Key Idea: Complexity describes how an algorithm's cost grows with the data — not how long it takes on one machine. That is why the growth rate, not the constant factor, decides which algorithm survives at scale.
Paper 1
- Short definitions and a trace.
- State, identify, outline — precise terms.
Paper 2
- Write or correct Python for a scenario — your paper is the Python version, option B.
- Construct, determine, suggest.
Both
- Trace tables and justified choices earn method marks even when the final answer slips.
📈 The complexities to know
| Order | Doubling the data… | Example |
|---|---|---|
| O(1) | changes nothing | Array access by index |
| O(log n) | adds one step | Binary search |
| O(n) | doubles the time | Linear search |
| O(n log n) | a little over doubles | The best a comparison sort can do |
| O(n²) | quadruples the time | Bubble and selection sort |
3n + 50 is O(n): the constant differs between machines and languages, and at scale the growth rate decides which algorithm wins. A better constant only moves the crossover point.
🔎 The two searches
| Linear search | Binary search | |
|---|---|---|
| Data must be | Anything | Sorted |
| Cost | O(n) | O(log n) |
| 1000 items | Up to 1000 checks | About 10 comparisons |
| Best when | Unsorted, searched once | Sorted, searched many times |
Important: Sorting costs O(n log n) — more than the single linear search it would replace. Binary search wins when the data is already sorted, or when it will be searched many times.
🔃 The two sorts
What distinguishes them
- Bubble compares adjacent pairs and swaps; each pass floats the largest to the end
- Selection finds the smallest in the unsorted part and swaps it into place
- Both are O(n²): 4 + 3 + 2 + 1 comparisons for 5 elements, which is n(n − 1)/2
- Bubble can stop early if a pass makes no swaps — O(n) on already sorted data
- Selection makes at most n − 1 swaps, which matters when moving a record is expensive
Practical judgement
- Better complexity is not always the better choice — on 20 items, simplicity wins
- Space complexity matters too: running out of memory is a hard failure, not a slow one
- Caching trades memory for speed — store a result rather than recompute it
- For real work use the language's own sort: better tested and better optimised
📝 Exam-style questions
An algorithm takes 2 seconds on 1000 records and 8 seconds on 2000 records. Determine its likely complexity, and predict the time for 8000 records.
🔒 Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.
A program searches an unsorted list of 500 names once, to answer a single query. A student suggests sorting it first so binary search can be used. Suggest whether this is worthwhile, justifying your answer.
🔒 Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.
✅ Quick check
Cover the answers.
Doubling the data doubles the time — which complexity? O(n) — linear.
Why does binary search need sorted data? It discards half the range by comparing with the middle value — meaningless if the data is unordered.
Which sort can finish in O(n) on already-sorted data? Bubble sort, if it stops early when a pass makes no swaps.
Why quote the worst case? It is the only one that guarantees the algorithm will never be slower than stated.
Why is 3n + 50 written as O(n)? Constants and lower-order terms differ between machines; at scale the growth rate decides.
Exam tips
- Read the RATIO: same time = O(1), double = O(n), quadruple = O(n²).
- Quote the worst case unless the question says otherwise.
- Binary search needs sorted data — say so every time you name it.
- Include the cost of sorting when comparing search strategies.
- n(n − 1)/2 is the comparison count for both O(n²) sorts. Learn it.
- Better complexity is not always the better choice — small n favours simplicity.