Why is skip-list search expected O(log n) rather than worst-case, and what degrades it?
answer
- Nothing enforces the shape after insert
- Where does the randomness come from?
- Flips are independent of the keys
- No input is a bad input here
- All towers height 1: what is left?
basics
~20 sA skip list picks each key's tower height by repeated coin flips, so its shape is random, not enforced. The O(log n) bound holds in expectation over those flips; if promotions dry up — a broken or degenerate random source — every tower is height 1 and search falls back to an O(n) chain walk.
solid answer
~50 sOn insertion, a key is promoted to the next level up with some fixed probability p (commonly 1/2), repeatedly, so tower heights follow a geometric distribution. Nothing enforces the shape: there is no rebalancing step that repairs a bad layout. The analysis says the expected top level is about log base 1/p of n and the expected search cost is O(log n), with deviations far above that being exponentially unlikely, which is why the structure behaves reliably in practice. The important nuance is *where the randomness comes from*: the coin flips are the structure's own, independent of the keys and their insertion order, so no adversary who merely chooses keys can force the bad case — unlike a deterministic pivot rule. What can force it is a broken, fixed-seed or predictable random source: if promotion effectively stops, every key sits at level 0 and search, insert and delete all degrade to O(n).
go deeper
Know that tower heights are decided by random coin flips at insert time, and that the O(log n) figure is an expectation rather than a promise about every operation.
Be ready to state the expected height and search cost in terms of the promotion probability, and to describe the degenerate case where every tower has height 1.
Show you can spot the real failure mode in production — a stubbed, fixed-seed or misconfigured random source silently flattening the structure — and name the metric that would reveal it.
Own the argument for accepting a probabilistic bound at all: where a hard per-operation latency ceiling is contractual, expectation with exponential concentration may still be unacceptable, and that call belongs to whoever owns the SLO.
## Where the levels come from When a key is inserted into a skip list, the structure decides how tall its tower of forward pointers should be by flipping a biased coin: start at height 1, and while the coin comes up "promote" (probability p, conventionally 1/2), add another level. Heights are therefore **geometrically distributed**: a fraction p of keys reach level 1 or higher, p² reach level 2 or higher, and so on. Nothing else shapes the structure. There is no rebalancing pass, no rotation, no height invariant that an insert must restore. The skip list is whatever the coin flips made it — which is exactly why its bound is stated in expectation. ## What "expected O(log n)" claims, precisely Three things, and it is worth separating them because interviewers push on all three: 1. **Expected height.** The tallest tower among n keys is about log base 1/p of n — roughly log₂ n at p = 1/2. 2. **Expected search cost.** Walking down from the top, the expected number of comparisons is about (1/p)·log_{1/p} n — roughly 2·log₂ n at p = 1/2. Constant work per level, logarithmically many levels. 3. **Concentration.** Deviations well above the expectation are not merely uncommon, they are exponentially unlikely in n. Skip lists are "with high probability" structures, which is why they behave like guaranteed-logarithmic structures on any realistic run despite carrying no guarantee. What it does **not** claim is a bound on any single operation. One search can be unlucky. The worst case, reachable in principle, is that every tower has height 1, the upper levels are empty, and the structure *is* a sorted linked list: O(n) search, O(n) insert position-finding, O(n) delete. ## Expected is not amortized, and not average-case-over-inputs Three different words, three different meanings, and mixing them is a classic stumble: - **Amortized** bounds the total cost of a worst-case *sequence*, divided over the operations. A growth-doubling dynamic array's append is amortized O(1): some single append copies everything, but no sequence of n appends costs more than O(n). - **Average-case** averages over an assumed *input distribution*. It is a claim about your data, and it fails when your data is not distributed as assumed. - **Expected**, in a randomized structure, averages over the algorithm's *own* random choices, for **any** input. This is the strongest of the three in one specific respect: it does not ask you to trust anything about the input. That distinction is the crux of the skip list's robustness argument. ## Why key-choosing adversaries do not break it A deterministic structure with a fixed rule can be attacked by whoever supplies the data. Choose the pivot as "always the first element" and a sorted input drives a partition-based sort to quadratic time; choose keys that collide and a hash table's expected-constant lookups become a linear scan of one bucket. A skip list's tower heights do not depend on the keys at all — not on their values, not on their hashes, not on the order they arrive. An attacker who sends a million carefully chosen keys gets the same distribution of tower heights as one who sends a million random ones. There is no input that is "bad" for a skip list. ## What actually degrades it Since the input cannot, the failure mode has to come from the coin: - **A degenerate or misconfigured random source.** A generator that is fixed-seeded and never advanced, stubbed to a constant in a test harness, or accidentally reduced to "never promote" flattens the structure. Every key ends at level 0 and every operation becomes a chain walk. This is a real bug class, and it fails *silently* — the structure stays correct, just linear. - **A wrong promotion probability.** Very small p produces too few levels and long right-walks; p very close to 1 produces very tall towers, exploding both memory and the descent cost. Both remain correct and both are slow. - **A predictable generator plus an attacker who can observe timing.** If the promotion stream is guessable, an attacker who can influence insert ordering can, in principle, steer which keys land tall or short. This is far more exotic than the hash-collision attack, but it is the reason the randomness should be a real source rather than a trivially reproducible one. - **A level cap set too low.** Implementations cap the maximum level for bookkeeping. A cap well below log₂ n turns the top lane into a long walk — the structure is now, in effect, a linear scan over the capped level. ## The line to say out loud "Expected O(log n), not guaranteed — the bound is over the structure's own coin flips, so no choice of keys can force the bad case; a broken random source can." That sentence contains the whole answer and pre-empts the follow-up.
- Is 'expected O(log n)' the same claim as 'amortized O(log n)'?No. Amortized bounds the total cost of a worst-case sequence spread over its operations — no randomness involved. Expected averages over the structure's own coin flips and holds for any single operation on any input. A skip list makes the expected claim: one search can be unlucky, but no sequence of inputs makes unluckiness likely, because the input never touches the flips.
- Why can an attacker degrade a hash-based structure but not a skip list?A hash structure's bucket placement is a deterministic function of the key, so an attacker who can compute or guess that function can pile every key into one bucket and turn expected-constant lookups into a linear scan. A skip list's tower heights come from internal coin flips that the key never influences, so crafted keys buy the attacker nothing. Its analogous weakness is a predictable or broken random source.
- What happens if the promotion probability is set to 0.9 instead of 0.5?Correctness is unaffected, performance is not. Expected pointers per key rise to 1/(1−p) = 10, so memory roughly quintuples versus p = 1/2, and towers become very tall, so the descent has many more levels to cross even though each level's right-walk shortens. Both ends of the p range are legal and slow; values near 1/2 to 1/4 are the usual compromise.
- How would you detect in production that promotions have stopped working?Export the current top level and the histogram of tower heights as metrics. Under healthy p = 1/2 the top level tracks log₂ n and heights halve at each step; a top level pinned at 1 while the key count grows into the millions is unambiguous. Latency alone is a weaker signal, because the degradation looks like ordinary gradual slowness.
The structure rolls its own dice rather than trusting your data. You cannot load dice you never touch — but if the dice come back blank, every roll is the same and the shortcuts vanish.
saying these in an interview costs you the question
- Says a skip list guarantees O(log n) search
- Claims sorted insertion order forces the worst case
- Uses expected and amortized as synonyms
- Thinks the structure rebalances itself after bad flips
- Believes the height depends on the key value