Algorithms · foundation
Algorithmic complexity: O, Ω, and Θ
Algorithmic complexity describes resource growth with input size: O gives an asymptotic upper bound, Ω a lower bound, and Θ a tight bound when both match.
Why it matters
Growth rate predicts whether an approach that is fast on a sample will remain usable on production-sized input and exposes time-versus-memory trade-offs.
Mental model
How to reason about algorithmic complexity: o, ω, and θ
Treat input size n as a dial and compare growth beyond some threshold. O is a ceiling shape, Ω is a floor shape, and Θ traps the cost between matching ceiling and floor shapes.
Analogy
A delivery route that visits every address grows with the neighborhood, while looking up a numbered mailbox stays roughly constant; the rule for how effort scales is the complexity.
Examples
See the boundary, not just the happy path
Worked example · Single pass
for item in items: total += itemThe loop examines each of n items once, so its running time is Theta(n) and its extra storage is Theta(1).
Worked example · All pairs
for a in items:
for b in items:
compare(a, b)Each of n outer iterations performs n comparisons, giving Theta(n^2) comparisons.
Useful contrast · Same tight class, different constants
scan A performs n operations; scan B performs 20n operationsBoth are Θ(n), although B can be much slower at real input sizes. Asymptotic notation does not replace benchmarking.
Common mistakes
Misconceptions to remove early
Using O when claiming a tight bound
O(n) gives an asymptotic upper bound and can describe even constant work. Use Θ(n) only after establishing matching upper and lower bounds.
Dropping the relevant input variable
A graph algorithm may depend on both vertices V and edges E. Collapsing O(V + E) into an unexplained O(n) hides the workload that drives cost.
Quick check
Can you predict the result?
1. A loop performs Theta(1) work for each of n elements and retains only fixed-size state. What are its complexities?
- • Theta(n) time and Theta(1) auxiliary space
- • Theta(1) time and Theta(n) auxiliary space
- • Theta(n^2) time and Theta(1) auxiliary space
2. What extra claim does Θ(n) make compared with O(n)?
Keep building