Why is interpolation search O(log log n) expected yet O(n) in the worst case?
answer
- Two bounds, two different assumptions
- Uniform data: the error scales like a square root
- Range takes a square root each probe
- Repeated square roots until constant equals log log n
- Skew makes the probe advance by one element
basics
~20 sOn near-uniformly spaced keys each interpolated probe narrows the remaining range from about n to about the square root of n, which compounds to O(log log n) expected probes. When spacing is skewed, the probe creeps toward one end an element at a time, giving O(n).
solid answer
~50 sThe two bounds answer different questions. The O(log log n) figure is an *expected* count under the assumption that keys are drawn roughly uniformly: the interpolated probe's error is on the order of the square root of the remaining count, so a range of size n shrinks to about sqrt(n), then to n to the one-fourth, and so on — the range size takes a square root each round, and taking a square root repeatedly until you reach a constant takes log log n rounds. The O(n) figure is what the same rule produces when the assumption breaks. With sharply growing spacing — say exponentially increasing values — the estimate lands almost at one end every time, the range shrinks by roughly one element per probe, and you have a linear scan with extra arithmetic. Crucially this is not an exotic adversarial input; ordinary skewed real-world data does it.
go deeper
Memorise the pair: about log log n probes expected on evenly spaced data, up to n probes when spacing is lopsided. Say which one is conditional and on what.
Derive the log log n: the expected probe error scales like the square root of the remaining count, so the range takes a square root each round. Then show the degenerate case advancing one element per probe.
Argue the risk, not just the math — the worst case is triggered by ordinary skewed measurements, not by an adversary, so a bound conditional on the input distribution is a weak thing to build a latency budget on.
Be ready to decide whether an expected-case win of a dozen probes is worth an unbounded tail on data your team does not control, and to say what evidence would change that decision.
## Two bounds, two different questions Interpolation search is quoted with two complexities, and candidates routinely blend them into one wrong sentence. Keep them apart: - **O(log log n) expected**, conditional on the keys being spaced roughly uniformly across the range. - **O(n) worst case**, with no conditions at all. The first is a statement about a *distribution*; the second is a statement about *any* input. Neither is amortized — amortization spreads the cost of a worst-case *sequence* of operations, and nothing here is being spread over a sequence. A single search either gets lucky with the distribution or does not. ## Where log log n comes from Suppose the current range holds m elements whose values are drawn uniformly across the endpoint values. The interpolated probe is the mean position the key would be expected to occupy. The deviation of the true position from that estimate behaves like the standard deviation of a sum of m independent gaps, which grows like the square root of m. So after one probe, the remaining range is not m/2 — it is on the order of sqrt(m). Now iterate. The range sizes go ``` n -> n^(1/2) -> n^(1/4) -> n^(1/8) -> ... ``` After k probes the range is about n raised to the power 1/2^k. Set that to a constant and solve: 2^k must be about log n, so k is about log log n. That is the whole derivation, and it explains why the numbers are so striking. For a million elements, binary search takes about 20 probes and interpolation search expects about 4 or 5. For a billion, binary search needs about 30; interpolation search's expectation barely moves, because log log n grows agonisingly slowly. A useful mental compression: binary search halves the *range* each step, interpolation search on uniform data halves the *number of digits* of uncertainty. ## Where O(n) comes from Nothing in the algorithm enforces the assumption, and the estimate is not clamped to any minimum progress. Consider a sorted range of transaction amounts drawn from a heavy-tailed distribution: thousands of amounts under a hundred, then a handful in the millions. The endpoint values are dominated by that handful of huge amounts. When you search for a small amount, `(key - a[lo]) / (a[hi] - a[lo])` is a tiny fraction, so the probe lands on or beside `lo`. The comparison advances `lo` by one. Next round the endpoints have barely changed, the fraction is still tiny, and the probe advances by one again. Repeat n times. That is the collapse in full: the range shrinks by a constant number of elements per probe rather than by a factor, and the recurrence degenerates from `T(m) = T(sqrt(m)) + O(1)` to `T(m) = T(m - 1) + O(1)`. The important part is that this is *not* an adversary constructing pathological input. Skewed distributions — power-law transaction amounts, file sizes, city populations, request latencies — are everywhere. The worst case is reachable through ordinary data, which is a very different risk profile from an algorithm whose worst case requires deliberate sabotage. ## The comparison you should be able to recite | | probes, uniform data | probes, skewed data | needs | per-probe cost | |---|---|---|---|---| | binary search | O(log n) | O(log n) | order only | add + shift | | interpolation search | O(log log n) expected | up to O(n) | order + key arithmetic | subtract + multiply + divide | Read the second column as the whole argument. Binary search's bound is indifferent to the data; interpolation search's is not, and that indifference is worth a lot in production. ## Directions people get backwards **"Expected is basically average, which is basically amortized."** Three distinct ideas. Expected: averaged over a distribution of *inputs*. Amortized: averaged over a *sequence* of operations, each individual one possibly slow, with a worst-case total. Interpolation search's headline bound is expected, and it inherits every weakness of a bound that assumes something about the input. **"O(n) is just the theoretical worst case, it will never happen."** For an algorithm whose worst case needs a crafted input, that shrug is often defensible. Here it is not — the trigger is skew, and skew is the normal condition of real measurements. **"Asymptotically better means faster."** Big-O hides the per-probe multiply and divide. On an array small enough to sit in fast cache, fewer probes may still be slower in wall-clock terms than more, cheaper ones. The asymptotic win needs a large n and a probe count that actually dominates.
- Is O(log log n) an amortized bound, an expected bound, or a worst-case bound?Expected, conditional on near-uniform key spacing. Amortized would mean averaging over a sequence of operations with a guaranteed worst-case total, which is not what is happening: a single search on skewed data is slow all by itself, and doing more searches does not spread that cost. Worst case is O(n), unconditionally.
- Sketch the recurrence for each of the two regimes.Uniform data gives T(m) = T(sqrt(m)) + O(1), because the expected probe error is on the order of the square root of the remaining count; unrolling gives log log n. Degenerate data gives T(m) = T(m - 1) + O(1), because the probe lands adjacent to an endpoint and only one element is eliminated; that unrolls to O(n).
- Would you ever see fewer wall-clock milliseconds from binary search despite more probes?Frequently, on small or cache-resident arrays. Interpolation's probe costs a multiply and a divide against binary search's add and shift, and a handful of probes into hot cache is very cheap. The asymptotic advantage needs a large array and probes expensive enough that their count dominates the arithmetic.
Binary search halves the range each step; interpolation search on uniform data halves the number of digits of uncertainty — until the data is lopsided, when it stops making progress at all.
saying these in an interview costs you the question
- States O(log log n) as a worst-case guarantee
- Calls the bound amortized rather than expected
- Claims the O(n) case needs a crafted adversarial input
- Thinks fewer probes always means less wall-clock time
- Says skewed data makes the search return wrong results