Why is exponential search O(log i) in the target's position rather than O(log n)?

## Naming the quantity Write `i` for the position of the answer — the index of the first entry whose key is at-or-past the target `T`. Write `n` for the total number of entries, which by assumption we cannot cheaply learn. The claim is that exponential search costs `O(log i)` probes, and that `n` appears nowhere. ## Counting the doubling phase The probes are at indexes 1, 2, 4, 8, ..., 2^k. The loop continues while the probed entry exists and its key is below `T`, so it stops at the first `k` with `2^k >= i`. That is `k = ceil(log2 i)`. So the doubling phase makes about `log2(i)` probes and never reads an index beyond `2^k < 2i`. The temptation is to say "doubling is exponential, so it must be expensive". The opposite is true: the *step size* grows exponentially, which is precisely why the *number of steps* is logarithmic. Compare with fixed-step probing (every 1000th index): reaching position `i` then takes `i/1000` probes — still linear in `i`, just with a nicer constant. ## Counting the binary search The surviving bracket is `[2^(k-1), 2^k]` (with `[0, 1]` in the degenerate first-probe case). Its width is `2^(k-1) <= i`, so a binary search over it takes at most `log2(i)` more probes. Add the two phases: `log2(i) + log2(i) = 2 log2(i)` probes, so `O(log i)`. ## Why this is not `O(log n)` `n` never appears because the algorithm never touches an index near `n` unless the answer is near `n`. Some cost lenses and what they say here: | Situation | Plain binary search over known size | Exponential search | |---|---|---| | Answer near the head (`i` tiny) | `log2 n` probes | about `2 log2 i` — a handful | | Answer in the middle | `log2 n` | about `2 log2 n - 2` | | Answer near the end (`i` close to `n`) | `log2 n` | about `2 log2 n` | | Size unknown | not applicable | works unchanged | The headline: exponential search buys independence from `n` and pays for it with a factor of about 2 when the answer is far out. For a log tailing workload — "give me everything since timestamp T", where T is usually recent and the answer is therefore near the head of the unread region — this trade is overwhelmingly favourable. ## Output-sensitive complexity as a lens An output-sensitive bound expresses cost in terms of the answer rather than the input. It is the honest way to describe algorithms whose work scales with what they find. Here it is what makes the technique interesting: an early hit in a petabyte-scale sorted log costs almost nothing, and the algorithm cannot be made to pay for the petabytes it never looks at. Be precise about the direction of the claim, though. `O(log i)` is an upper bound on probes, and it says nothing about the cost of a single probe — if one probe pulls a cold page across a network, twenty probes may still be slow in wall-clock terms. It also promises nothing about `i` itself: an adversarial or simply unlucky query whose answer sits at the far end pays the full `2 log2 n`. ## Where else the same doubling appears The same "jump ahead in doubling steps, then binary search the overshoot" idea shows up inside merge routines. When merging two sorted runs and one run keeps winning comparisons, comparing one element at a time wastes a comparison per element; galloping ahead in doubling steps finds the crossover point in logarithmic probes and copies the skipped stretch in one move. Several mainstream ecosystems ship merge-based library sorts built on exactly this — the list sorts in Python and in Java both gallop when a run pulls ahead — which is a good illustration that the technique is a general "find the boundary cheaply when it is probably near" tool, not a niche trick for unbounded arrays. ## The comparison to state in an interview If the size is known and cheap and queries land anywhere, use plain binary search: `log n` beats `2 log i` on average. If the size is unknown, expensive, or stale, or if answers cluster near the front, exponential search is the better bound and the simpler dependency graph.