Unit 5 · Data and algorithms
Why binary search is O(log n), not O(n)
Having a loop does not make code O(n). Binary search’s loop halves the remaining list on every pass, so a million items shrink to one in about 20 steps. That growth is logarithmic: O(log n).
The mix-up
What people often think
“Binary search has a loop, so it is O(n).”
What the tutor says
Its loop throws away half the list each time round. Halving reaches one item in log n steps, not n.
How it works
Count the halvings: 1,000,000 → 500,000 → 250,000 and so on. Doubling the list adds only one more step.
This only works when the guess is the middle. Any other pick can leave you with the bigger part, and the guarantee is gone.
Close cousins of this mix-up
The tutor watches for these in the same lesson.
“Any card in the range is a fine guess.”
The middle splits the range in two equal halves. Any other pick can leave you with the bigger half.
Practise it with a tutor watching
Big O by feel
Look at a piece of code and say roughly how its work grows as the data grows.
Free, no account needed.