Algorithm Complexity

Strategy

Talk about time and space complexity through out the program look at the input parameters to the function

Terminology

$O(nlogn + n^2)$ asymptotically is $O(n^2)$. If you write $O(n^2)$ explain its the asymptotic time complexity.

Applications

Common time complexity patterns:

• $O(2^N)$, $O(3^N)$: Permutation (e.g., NP hard problems)
• $O(N^2)$, $O(N^3)$: Recursion / generate subsets, nested loops
• $O(NlogN)$: Sorting / heap
• $O(N)$: Iteration, pointers/sliding window, common array operations
• $O(logN)$: Binary search / exponentially sized steps search
• $O(1)$: Hashmap or index of array

Time Complexity Names

• $O(2^N)$, exponential time
• $O(N^2)$, quadratic time
• $O(NlogN)$, linearithmic time
• $O(N)$, linear time
• $O(logN)$, logarithmic time
• $O(1)$, constant time

Space Complexity

Space = Input + Auxilary + Output

I would make the argument that the reason a lot of the times that Input is dropped from the space complexity is that it can be passed by reference. Whatever you pick make sure to define what you are considering and what is not.

Consider the following example. What is the space complexity?

int summation(vector<int> nums)
{
    int sum = 0;

    for ( auto n : nums )
        sum += n;

    return sum;
}

I make the assertion that summation as written is:

O( input + aux + output ) = O(n + 1 + 1) ==> O(n)

However, we can go to constant space complexity by simply declaring it as: int summation(vector<int> & nums).