Time Complexity
Decidable isn’t enough — is it decidable *fast*? Big-O, complexity classes, and why the exponents matter.
From Computable to Tractable
A problem being decidable says an algorithm exists. Complexity theory asks the sharper question: how do its time and space requirements grow with input size n? A decidable problem that takes 2ⁿ steps is, for n = 100, beyond the lifetime of the universe. “Solvable in principle” and “solvable in practice” are different universes.
The Growth Hierarchy
| Class | Name | n=10 | n=1000 | Feel |
|---|---|---|---|---|
O(1) | Constant | 1 | 1 | Hash lookup |
O(log n) | Logarithmic | 3 | 10 | Binary search |
O(n) | Linear | 10 | 1000 | One scan |
O(n log n) | Linearithmic | 33 | ~10⁴ | Good sort |
O(n²) | Quadratic | 100 | 10⁶ | Nested loops |
O(2ⁿ) | Exponential | 1024 | ~10³⁰¹ | Brute-force subsets |
O(n!) | Factorial | ~10⁶ | — | All permutations |
Complexity Classes
Problems get grouped by the resources needed to solve them:
| Class | Means |
|---|---|
| P | Solvable by a deterministic TM in polynomial time — “efficiently solvable” |
| NP | A proposed solution is verifiable in polynomial time (guess + check) |
| PSPACE | Solvable in polynomial space (time may be exponential) |
| EXPTIME | Requires exponential time — provably intractable |
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME. Whether any of those ⊆ is actually = is mostly open — including the million-dollar one, P vs NP, the next guide.
Best, Worst, Amortized
“Complexity” needs a case. Worst-case (the guarantee) is what you usually quote. Average-case assumes an input distribution (quicksort is O(n log n) average, O(n²) worst). Amortized averages over a sequence — a dynamic array’s push is O(1) amortized even though occasional resizes are O(n), because they’re rare enough to spread out.
Interview Questions
Why care about complexity if a problem is already decidable?
Decidable means an algorithm exists; complexity says whether it finishes before the heat death of the universe. An O(2ⁿ) decision procedure is useless at n=100. Tractability, not mere solvability, is what makes an algorithm usable.
Where’s the important line in the growth hierarchy, and why?
Between polynomial (nᵏ) and exponential (2ⁿ). Polynomial algorithms scale with hardware; exponential ones hit a wall where each added input element multiplies the work. This is the boundary P vs NP is about.
P vs NP in one sentence (setup for the next guide).
P is problems solvable in polynomial time; NP is problems whose proposed solutions are checkable in polynomial time. Whether every efficiently-checkable problem is also efficiently-solvable (P = NP) is open.
Worst vs average vs amortized complexity?
Worst-case: the guaranteed upper bound over all inputs. Average-case: expected cost over an input distribution (quicksort O(n log n) average, O(n²) worst). Amortized: average cost per operation over a sequence, spreading rare expensive operations (dynamic-array resize) across many cheap ones.