Big-O Time Complexity
Measuring algorithm efficiency
We compare algorithms by how their time (or space) requirement grows as the input size n increases. Big-O notation describes this worst-case growth rate, ignoring constants and lower-order terms — it captures how an algorithm scales.
Common complexities (best to worst)
| Big-O | Name | Behaviour as n grows | Example |
|---|---|---|---|
| O(1) | Constant | Doesn't grow | Array index lookup; hash table access |
| O(log n) | Logarithmic | Grows very slowly | Binary search |
| O(n) | Linear | Grows in proportion | Linear search |
| O(n log n) | Linearithmic | Slightly worse than linear | Merge sort, quicksort (average) |
| O(n²) | Quadratic | Grows steeply | Bubble/insertion sort; nested loops |
| O(2ⁿ) | Exponential | Explodes | Naïve recursive Fibonacci; brute-forcing combinations |
| O(n!) | Factorial | Intractable | Travelling salesman (brute force) |
How to work it out
- A single loop over n items → O(n).
- A loop inside a loop (both over n) → O(n²).
- Halving the problem each step (e.g. binary search) → O(log n).
- Ignore constants: O(2n) and O(n + 5) are both just O(n); keep only the dominant term (O(n² + n) → O(n²)).
Space complexity
The same notation describes memory used relative to n (e.g. merge sort is O(n) space because it creates new sub-lists; an in-place sort may be O(1) space). There's often a time–space trade-off.
Tractable vs intractable
- Tractable problems have a solution in polynomial time (O(n), O(n²), O(n log n)…) — feasible for large inputs.
- Intractable problems only have solutions of exponential/factorial time — impractical for large n, so heuristics (good-enough approximations) are used instead.
Worked example
An algorithm has a loop over n items, and inside it another loop over n items. What is its time complexity?
- A nested loop, each running n times → n × n = O(n²) (quadratic). ✓
Common mistakes
- Keeping constants or lower-order terms — Big-O drops them (O(3n²+2n) → O(n²)).
- Confusing O(log n) with O(n) — logarithmic comes from halving, not iterating.
- Assuming a faster Big-O is always better for small n (constants can matter there).
Exam tips
- Learn the order of the common complexities and an example of each.
- Determine complexity from loop structure (single = O(n), nested = O(n²), halving = O(log n)).
- Explain tractable vs intractable and why heuristics are used for intractable problems.
Key facts to remember
- Big-O describes worst-case growth as n increases, ignoring constants; keep the dominant term.
- Order (best→worst): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
- Tractable = polynomial time; intractable = exponential/factorial → use heuristics.