Big O Notation and Comparing Algorithms
1. Why Compare Algorithms At All?
Two algorithms can both solve the same problem correctly and still be wildly different in practice. Choosing between them needs measurable criteria, and the syllabus names two:
- Time taken to complete the task — time complexity
- Memory used while running — space complexity
Timing an algorithm with a stopwatch is unreliable: the result depends on the processor, the language, and what else the machine is doing. So instead we measure how the work grows as the amount of data grows. That measure is independent of any particular computer.
2. Big O Notation
Big O notation describes the order of growth of an algorithm — how the time or memory requirement scales with the number of data items, n.
3. The Orders You Need
| Big O | Name | Behaviour as data doubles | Typical example |
|---|---|---|---|
| O(1) | Constant | No change at all | Reading one array element by index; pushing to a stack |
| O(log n) | Logarithmic | Adds one extra step | Binary search |
| O(n) | Linear | Takes twice as long | Linear search; totalling an array |
| O(n log n) | Linearithmic | Slightly more than doubles | Efficient sorts such as merge sort |
| O(n²) | Quadratic | Takes four times as long | Bubble sort; insertion sort |
| O(2ⁿ) | Exponential | Becomes unusable very quickly | Brute-force search of all combinations |
What the growth actually looks like
| n | O(log n) | O(n) | O(n²) |
|---|---|---|---|
| 10 | 3 | 10 | 100 |
| 100 | 7 | 100 | 10 000 |
| 1 000 | 10 | 1 000 | 1 000 000 |
This table is the whole argument for caring about complexity. At n = 1000 a logarithmic algorithm needs 10 steps and a quadratic one needs a million.
4. Working Out the Complexity
Count how many times the innermost work is done, in terms of n.
A single loop is O(n)
A nested loop is O(n²)
Halving the data is O(log n)
5. Complexity of the Required Algorithms
| Algorithm | Time (worst case) | Time (best case) | Space |
|---|---|---|---|
| Linear search | O(n) | O(1) — first item | O(1) |
| Binary search | O(log n) | O(1) — middle item | O(1) |
| Bubble sort | O(n²) | O(n) — already sorted, with flag | O(1) |
| Insertion sort | O(n²) | O(n) — already sorted | O(1) |
6. The Time–Space Trade-off
Reducing time often costs memory, and reducing memory often costs time. A worked comparison:
| Approach | Time | Space |
|---|---|---|
| Search an unsorted array directly | O(n) | O(1) |
| Build an index first, then search it | O(log n) per search | O(n) for the index |
Which is better depends on use: for a single lookup the direct search wins, because building an index costs more than it saves. For thousands of repeated lookups the index wins easily.
7. Exam Focus
Quick self-check
- Define time complexity and space complexity.
- Give the Big O time complexity of linear search, binary search and bubble sort.
- An algorithm takes 4n + 12 steps. State its Big O complexity.
- Why are bubble sort and insertion sort O(1) in space?
- If an O(n²) algorithm takes 2 seconds on 1 000 items, roughly how long on 2 000?
- Explain one situation where using more memory produces a faster program.