Binary search halves the list each time, so my first instinct was that it does about n/2 work. I know the answer is log n but I cannot see where the logarithm comes from, and halving once really does remove half the list.
What is the quantity that the logarithm is counting?
Accepted Answer
It counts how many times you can halve n before you reach 1, and that is the definition of a base 2 logarithm.
You are not doing n/2 work. You are doing one comparison, and then the same problem at half the size. The sizes go n, n/2, n/4, n/8 and so on. Ask how many steps until that reaches 1 and you are asking for k in n / 2 to the k = 1, which gives k = log₂ n.
A million items takes about 20 comparisons. Halving a million once still leaves half a million, which is why "it halves the list" and "it is fast" feel unrelated until you count the steps instead of the elements.
Worth heading off the follow up, because it trips people right after this clicks.
The base of the logarithm does not matter to the big O. Splitting into three parts instead of two gives log₃ n, and log₃ n is log₂ n divided by a constant. Big O ignores constant factors, so both are O(log n).
Which means ternary search is not asymptotically better than binary search, despite cutting more off each time. It does more comparisons per step, and that is where the saving goes.
The tell is in the recurrence. T(n) = T(n/2) + 1. Constant work, then the same problem half as big. Anything of that shape is logarithmic.
The discussion on each answer is open to members.
Join free to read the rest