Complexity Analysis
How an algorithm's cost grows with the size of its input, stated so that a faster machine does not change the answer.
Complexity in Numbers: Six classes as n doubles
Complexity analysis counts operations as a function of input size and then discards everything that does not affect the growth. O(n^2) makes no claim about seconds. It says that doubling n roughly quadruples the work. That is the part of a measurement that survives a change of machine, language or compiler, which is why it is the part that gets written down.
One algorithm has several costs and they are separate statements. Best, average and worst case are three different inputs. Expected time averages over the algorithm's own coin flips instead, which is why randomized quick sort has no bad input, only unlucky seeds. Space is counted the same way, and the recursion stack counts towards it: merge sort's extra n of buffer and quick sort's O(log n) of frames are both auxiliary space.
Two tools handle the awkward cases. Amortized analysis spreads a rare expensive operation over the cheap ones around it, so a dynamic array whose append occasionally copies everything still costs under 3n for n appends, making the append O(1) amortized. Recurrence relations handle the recursive ones: write T(n) = a T(n / b) + f(n) and the master theorem says which level of the recursion tree dominates the sum.
After this you can
- Count the operations in a loop or a recursion and state the growth in Big O
- Separate worst case from average case, and both of those from expected time
- Show an operation is O(1) amortized with an aggregate, accounting or potential argument
- Write the recurrence for a recursive algorithm and solve it with the master theorem
- Report the auxiliary space an algorithm uses, stack frames included
In this order
Also in this category
Algorithm Properties
Where people go wrong
Big O hiding a large constant
The discarded constants are real time. A hash lookup and an array index are both O(1) and the index is several times quicker. A contiguous O(n^2) pass over 1,000 elements can beat an O(n log n) one that chases pointers. Asymptotics say which algorithm wins as n grows, not which is faster at the n in front of you.
Quoting the average case as if it were a guarantee
Quick sort is O(n log n) on average and O(n^2) when the pivot is always the extreme. A hash map lookup is O(1) until every key lands in one bucket. When the input can be chosen by somebody else, the worst case is the number that matters.
Reading amortized as worst case
O(1) amortized means n operations cost O(n) in total, not that each one is quick. The append that triggers a resize still copies the whole array, which is why an amortized bound is no comfort inside a loop with a deadline.