Measuring complexity with Big-O
We do not time algorithms in seconds, because computers differ. We count steps and ask how the count grows with the input size n. Big-O keeps only the fastest-growing part: 3n² + 5n + 7 is O(n²).
| Big-O | Name | Example |
|---|---|---|
| O(1) | constant | read the first item of a list |
| O(log n) | logarithmic | binary search |
| O(n) | linear | linear search |
| O(n log n) | linearithmic | merge sort |
| O(n²) | quadratic | bubble sort |
| O(2ⁿ) | exponential | trying every subset |
| O(n!) | factorial | trying every order (route) |
We also talk about space complexity: how much memory grows with n.
Polynomial vs exponential: tractable and intractable
A problem is tractable if some algorithm solves it in polynomial time, O(nᵏ) for a fixed k. It is intractable if every known algorithm needs more than polynomial time, such as O(2ⁿ) or O(n!).
Why does it matter? Doubling n makes n² four times bigger. But adding just 1 to n doubles 2ⁿ. At 10⁹ steps per second, n = 60 with 2ⁿ steps takes about 36 years. A faster computer barely helps.
For intractable problems we use heuristics: rules of thumb that give a good-enough answer quickly (for example, 'always go to the nearest unvisited city').
Classic hard problems, P and NP
- Travelling salesman: shortest round trip through n cities. Brute force checks (n−1)!/2 routes.
- Knapsack: pick items with the most value that fit in a bag.
- Timetabling and graph colouring: give exams time slots so no student has a clash.
P is the class of problems that can be solved in polynomial time. NP is the class whose answers can be checked in polynomial time. Checking a given route is fast; finding the best one seems slow. Whether P = NP is one of the biggest open questions in computer science.
Computable and non-computable: the halting problem
A problem is computable if some algorithm always gives the right answer in a finite number of steps. Some problems are non-computable: no algorithm can ever solve them for every input.
The halting problem asks: given any program and its input, will it stop or run forever? Alan Turing showed (1936) that no general machine H can answer this. Idea of the proof: suppose H exists. Build a program X that asks H about itself and then does the opposite (loops if H says 'stops', stops if H says 'loops'). Then H is wrong about X. So H cannot exist.
Lesson: some limits are not about speed. Even an infinitely fast computer cannot solve a non-computable problem.
Try it: feel the explosion
Write the letters A, B, C. List every order (ABC, ACB, …): 6 orders. Add D: 24 orders. Add E: 120. Each new letter multiplies the work. That is n! growth, the same reason route-finding gets hard.
Key formulas and definitions
- Big-O keeps the fastest-growing term: 4n² + 3n + 1 → O(n²)
- Polynomial time: O(nᵏ) (tractable)
- Exponential: O(2ⁿ); factorial: O(n!) (intractable)
- Travelling salesman routes for n cities: (n − 1)!/2
- Time ≈ steps ÷ (steps per second)
Worked examples
1. Give the Big-O of 5n³ + 2n² + 100.
Keep the fastest-growing term and drop the constant: O(n³).
2. An O(n²) algorithm takes 1 s for n = 1000. About how long for n = 3000?
n is 3 times bigger, so time is 3² = 9 times: about 9 s.
3. An O(2ⁿ) algorithm takes 1 s for n = 30. About how long for n = 40?
10 more items → 2¹⁰ = 1024 times longer: about 1024 s ≈ 17 minutes.
4. How many different round trips for 5 cities (brute force)?
(5 − 1)!/2 = 24/2 = 12 trips.
5. At 10⁹ steps per second, how long do 2⁵⁰ steps take?
2⁵⁰ ≈ 1.13 × 10¹⁵. Time ≈ 1.13 × 10⁶ s ≈ 13 days.
6. Is 'sort a list' tractable? Is 'find the best exam timetable for 500 students' tractable?
Sorting is O(n log n), polynomial, so tractable. The best timetable (graph colouring) has no known polynomial algorithm, so it is treated as intractable; schools use heuristics.
Common mistakes
- Thinking a faster computer fixes an exponential algorithm: it only adds a few more items.
- Confusing intractable (too slow) with non-computable (impossible for any algorithm).
- Keeping constants in Big-O, like O(3n²); just write O(n²).
- Believing NP means 'not polynomial'. NP means the answer can be checked in polynomial time.