Complexity, explained.
Measure how the work grows. State the assumptions. Then justify the bound. This guide connects the notation in Lectures 04 and 06 to concrete code.
Growth, not a stopwatch reading
Input size n might mean array length, number of objects or number of tokens. Time complexity counts work under a cost model; space complexity counts stored information. Neither is a measurement in seconds or megabytes without a concrete implementation model.
Move the slider to see why a quadratic method becomes expensive. The curves show exact mathematical functions with coefficient 1, not benchmark results.
At n = 16: log₂ n ≈ 4.00, n = 16, n² = 256. These are operation-count functions, not measured seconds.
The growth-rate reference
| Class | Name | Reasoning example | f(2n) / f(n) |
|---|---|---|---|
| O(1) | Constant | A fixed number of operations, such as reading an array entry. | 1 |
| O(log n) | Logarithmic | Halve the remaining search region at each step. | ≈ 1 |
| O(n) | Linear | Visit every input item a constant number of times. | 2 |
| O(n log n) | Linearithmic | Linear work at each of logarithmically many levels, as in merge sort. | Slightly above 2 |
| O(n²) | Quadratic | Inspect all pairs or scan n items for each of n items. | 4 |
| O(n³) | Cubic | Enumerate all triples, as in brute-force 3-SUM. | 8 |
| O(2ⁿ) | Exponential | Enumerate every subset of n distinct items. | 2ⁿ |
| O(n!) | Factorial | Enumerate all permutations of n distinct items. | (2n)! / n! |
The ratios use the representative function itself; a Big O upper bound alone does not determine an exact doubling ratio. Subset and permutation enumeration are supplementary examples.
O, Ω and Θ answer different questions
O(g(n)): an eventual upper bound. Ω(g(n)): an eventual lower bound. Θ(g(n)): matching bounds up to constant factors. These are mathematical relations, not synonyms for worst, best and average cases.
For n ≥ 1, 3n² + 2n + 1 is between 3n² and 6n², so it is Θ(n²). It is also O(n³), but that upper bound is looser.
Best, average and worst cases
For a fixed n, best case minimizes the cost and worst case maximizes it. Average case needs a probability distribution. Linear search can succeed at the first entry in Θ(1), but inspecting all entries takes Θ(n). Under a uniform successful-position model it makes (n+1)/2 inspections on average.
Time and space are independent
Three nested loops can still use constant auxiliary memory. Recursive binary search needs a logarithmic call stack, while the supplied iterative version uses constant auxiliary space. State whether the input array itself is included.
Amortized is not average case
A resizing-array stack may spend Θ(n) on one push, but geometrically spaced resizes give Θ(1) amortized cost per operation over a worst-case sequence. No random input assumption is needed.
Sorting implementations compared
| Implementation | Best | Average | Worst | Auxiliary space | Stable |
|---|---|---|---|---|---|
| Insertion sort | Θ(n) | Θ(n²) | Θ(n²) | Θ(1) | Yes |
| Selection sort | Θ(n²) | Θ(n²) | Θ(n²) | Θ(1) | No |
| Merge sort | Θ(n log n) | Θ(n log n) | Θ(n log n) | Θ(n) | Yes |
| Quick sort | Θ(n log n) | Θ(n log n) expected | Θ(n²) | O(log n) expected stack; O(n) worst | No |
Values refer to the named supplied implementations. Insertion’s average assumes random distinct keys; Quick’s expected result relies on its initial shuffle. A modified implementation can have different guarantees.
How to analyze a loop
- Define input size and count one meaningful operation.
- Write the number of iterations, including dependent bounds.
- Add costs of sequential blocks; sum nested work.
- Keep a leading-term approximation or use a bound as appropriate.
- Account separately for allocations and recursion.