Big O vs Big Omega vs Big Theta
In academia, Big O is upper bound of time, Big Omega is lower bound, and Big Theta is combined both upper and lower bound of time
Space complexity
Similar to Big O and time complexity, how much memory something needs to allocate to run.
What do you need to do with O(2N)
Drop the constant, O(2N) = O(N)
In addition to dropping constants, when using Big O you should also
Drop non dominant terms:
O( N^2 + N) => O(N^2)
O(N + logN) => O(N)
O(5*2^N + 1000N^100) => O(2^N)
When using Big O, when to add and when to multiply?
If “do this, then when youre done do that” add. If “do this for each time you do that” then multiply.
What is amortized time?
Sometimes things take multiple different times. With an array list, it is O(1) unless the array needs to be expanded, at which case it will take O(N) time. When it is expanded the size is doubled.
The doubling happens in powers of 2, so at elements 1,2,4,8,16…X. The sum of this is x + x/2 + x/4 … + 1 = 2x.
Therefore, X insertions take O(2X) time, but the amortized time for each insertion is O(1).
Where do logN runtimes come from?
Anytime you cut the number of steps in half each time (think binary search)
What is the general rule for BigO for recursive functions that make multiple calls?
Ex: return f(n-1) + f(n-1);
The runtime will often, though not always, be O(branches^depth) where branches is the number of times each recursive call branches, in the case from this question that would be 2. So O(2^N).
In bigO, the base of an exponent (does/does not) matter?
It does matter, 2^N != 3^N.
For ex: 8^N = 2^3^N = 2^3n = 2^2N * 2^N and 2^N is not a constant factor so it is not dropped.
In contrast, the base of logs does not matter. We dont care about log base 7 n, we just say logN.
With bigO, be sure not to use N
in multiple ways. If asked for the runtime to sort strings in an array, then sort the array itself, you cant use N for both the length of the strings and the length of the array.
Define terms: s = length of string, a = length of array.
To sort each string = O(s log s)
Need to do for each string in array gets us to O(a*s * log s)
Sort strings in array (dont forget you need the time to compare each string which is O(s) time) is O(a*s log a)
Add it all together and you get O(a*s (log a + log s))
