AlgoScope

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.

17 topics5 lessons4 families

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
124816321lg nnnlgnn^22^n110112021424

n = 2. Doubling n added 1 to log n (0 to 1), doubled n, roughly doubled n log n (0 to 2), quadrupled n squared (1 to 4) and squared 2 to the n (2 to 4).

Open in the player →or start at step 3

In this order

  1. Big OAn upper bound on growth; O(n^2) means at most proportional to n^2 for large n, read off as what happens when n doubles.
  2. Time ComplexityOperation count as a function of input size; the classes separate within a few doublings of n.
  3. Space ComplexityMemory used as a function of input size, counting temporary arrays and the call stack.
  4. Auxiliary SpaceExtra memory beyond the input itself, such as merge sort's buffer or a recursion's frames.
  5. In-placeO(1) auxiliary space; the input is rearranged within itself.
  6. Best, Average and Worst CaseThe same algorithm costs differently on different inputs; each case is a separate statement.
  7. Big OmegaA lower bound; the cost is at least a constant times the reference for large n.
  8. Big ThetaA tight bound; the function stays between two scaled copies of the reference from some n0 on.
  9. Expected TimeAverage over the algorithm's own random choices, for any input.
  10. Amortized AnalysisAverage cost per operation over a sequence, even when a few operations are expensive.
  11. Aggregate MethodTotal cost of n operations divided by n.
  12. Accounting MethodEach cheap append deposits credit that a later resize spends, so the average stays O(1).
  13. Potential MethodA potential function on the data structure state pays for expensive operations.
  14. Recurrence RelationsT(n) = a T(n / b) + f(n), the cost equation of a recursive algorithm, read off its recursion tree.
  15. Master TheoremCompare f(n) with n^(log_b a), the leaf count of the recursion tree, to read off T(n) in three cases.

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.

Or a different category

Algorithmic Paradigms

You have the cost of a solution and want a different shape of solution rather than a tighter bound on this one.

Sorting

You want to watch the cases on real algorithms: insertion sort's best case, quick sort's worst, merge sort's extra memory.

Lessons that teach these