Complexity Questions Interviewers Love

A linear search needs up to a million comparisons in the worst case, and half a million on average if the target is uniformly distributed. A binary search needs at most twenty, because each comparison halves the remaining interval.

import math

for n in (1000, 1000000):
    linear = n
    binary = math.ceil(math.log2(n + 1))
    print(n, linear, binary)

The output shows a thousand values needing a thousand comparisons against ten, and a million values needing a million comparisons against twenty. The logarithm is doing all the work: solving two to the power k greater than or equal to n gives k, so the number of probes is the ceiling of the base two logarithm of one more than the size.

This is the question interviewers use to see whether you can connect an asymptotic bound to a concrete number. Saying binary search is O of log n is the easy half. The stronger answer adds the arithmetic, because the interviewer is really asking whether you can size a system: at twenty comparisons per lookup and a million lookups per second, that is twenty million comparisons per second, which is comfortable on any modern core. The linear version at a million comparisons per lookup is not.

The trade-off to state is that binary search requires sorted data, and sorting a million elements costs about twenty million comparisons with a comparison sort. So for a single lookup, scanning is cheaper overall. The logarithmic search only pays for itself when you will query the same collection repeatedly, which is exactly the situation where keeping an index is the right design.

Start by separating the size from the shape. Size is what you control and what you scale: the number of items, the number of edges, the number of distinct values. Shape describes how those items are arranged, and it is where input-sensitive costs live. A good analysis names both, because the bound you give is only meaningful if the reader knows which shape you assumed.

Then identify what varies with the shape. Sorting cost depends on how many runs of ordered data the input contains. A merge of two lists depends on how much of each list is consumed before one runs out. In each case the honest answer is a worst-case bound plus an average-case bound with the distribution stated, and for input-sensitive algorithms a third figure tied to a measurable property of the data.

Watch the trap of summing worst cases. If a function sorts each of a hundred sublists independently and the sublists are each sorted, the total is a hundred times linear rather than a hundred times n log n. People routinely quote the product of two worst cases and produce a bound that is far too pessimistic, because the two worst cases rarely happen at the same time.

Finally, decide what to do with the analysis. If the shape affects cost materially, either normalise the shape before the expensive step, or pick an algorithm whose cost does not depend on it, such as a hash table instead of a sorted list. And say plainly that the bound assumes a distribution you have not measured. A bound of O of n log n if the input is nearly sorted and O of n squared otherwise, with a plan for detecting which case you are in, is a stronger answer than a single optimistic number.