Plenty of entries on this site admit to a worst case strictly worse than their typical cost. Said that way, every one of them sounds like the same kind of risk. They aren't. The question that actually matters for a visitor deciding whether to worry is never just "can this be slow" — it's what has to be true for it to happen, and what happens after it does. Does a specific, nameable input trigger it every single time, or does it take bad luck that re-running makes go away? And once triggered, does the structure stay bad forever, or does the next operation (or the sequence as a whole) bounce right back? Those two questions sort every "has a worst case" claim on this site into four genuinely different buckets — and conflating them is the actual mistake, not the worst case itself.
The sharpest kind: a single, nameable, repeatable input drives the cost into a worse
class, and nothing about continuing to use the structure afterward fixes it.
Quicksort's fixed last-element pivot is the clearest
example already measured on this site: feed it an already-sorted array and
"every partition splits into a range of size
n-1 and a range of size 0... total work becomes
O(n²)." That page's own live race puts a number on it — at n = 5,000,
already-sorted input costs 12,497,500 comparisons against median-of-three's
51,822, roughly 241× more — and the trigger isn't exotic or
hard to construct: it's the single most ordinary input shape there is.
A Binary Search Tree fed sorted data has
the identical shape, and that page's own Pitfalls section already names the mechanism in prose —
"insert already-sorted data... and
every new node becomes the previous one's right child... every operation degrades to
O(n), exactly as bad as a linked list" — without ever putting a number on it. The
demo below does. Both of these share the defining trait of a permanent cliff: the bad shape isn't a
one-operation blip. A quicksort call on sorted input does all of its work the slow way,
start to finish; a BST built from sorted inserts stays a straight line forever afterward — every
future search, insert, or delete pays the same O(n) cost the first one did, until something
external (a rebuild, a rebalance) fixes the shape. Nothing about continuing to use either structure
heals it.
Same reference insert logic both times — only the order of the n values being inserted changes. "Sorted" inserts 0, 1, 2, … n−1 in that order; "random" shuffles the identical set of values first. Height is measured with a plain level-order walk (no recursion, so a 20,000-deep sorted chain can't blow the measuring code's own call stack the way a naive recursive height function does — a real bug hit and fixed while building this page, left out of the numbers below since it isn't the actual claim being measured).
One example run measured while building this page, at n = 5,000: sorted insertion produces a
tree of height exactly 5,000 — every single node has exactly one child, the
signature of a straight line, not a tree. A random insertion order of the identical 5,000 values
produced height 29 that run (it varies run to run; log₂(5,000) ≈ 12.3,
so this is a little under 2.4× that reference line, consistent with the well-known
≈2.99 ln n expected-height bound for a randomly built BST). The gap between the two
numbers is not a constant-factor slowdown the way the quicksort pivot comparison is — it's exactly
the missing factor of n that turns an O(log n)-shaped structure into an
O(n) one, and it only takes one insertion order to get there.
A different kind of cliff exists in exactly the same complexity class but is reached a
completely different way. Skip List's own Pitfalls
section is explicit that its coin-flip-based balancing "needs no adversarial input" to produce a
worst case — "the structure degenerates into a
plain sorted linked list, an O(n) scan for every search... it's just vanishingly
unlikely here in the honest sense of a real, computable probability:
(1 - p)n per node landing at level 0" — the same event that would make
every one of n coin flips come up tails. Treap names the
identical risk for its own random priorities, and random-pivot Quicksort is the third member of
this set: all three replace "is there an input that triggers the bad case" (yes, always, for a
permanent cliff above) with "is there a run that triggers it" — and for all three, that
run is so improbable at any real n that it is never actually observed, yet it is not
mathematically zero the way the next section's hard guarantees are. The practical
difference that matters: an adversary who can choose your input can force a permanent cliff on
demand. An adversary cannot force a probabilistic one — only hope for it — and the honest fix for a
permanent cliff (randomize the pivot, randomize the priority, flip real coins for the level) is
precisely what turns it into this strictly safer kind.
A third shape looks like a cliff from a single operation's point of view but isn't one at all
once the whole sequence is considered. Dynamic
Array's own Why
push is O(1) amortized, not O(n) section measures this directly: any individual
push that triggers a resize really does cost a real O(n) copy, not a
rounding error — but Amortized Analysis, Explained's
own aggregate-method proof against that identical push simulator shows the total cost
across any n pushes stays O(n), for an average of O(1) per call, "for
reference, 2,023 element-touches [across 1,000 pushes], for an aggregate amortized cost of
2.023." The very next push after a resize is cheap again — nothing about the spike lingers.
Splay Tree makes the same point from the opposite
direction: it offers no per-operation guarantee at all — a single search can genuinely cost
O(n), and that page's own demo is loaded with a worst-case height-7 chain specifically
to show it happening. Yet Amortized Analysis,
Explained's potential-method section proves, with a real verified numeric instance, that the
amortized cost over any sequence of operations still lands at O(log n) — the
expensive splay that just happened is exactly what pays for the cheap ones a well-known
access-pattern argument (and the site's own proof) shows follow it. The defining trait that separates
both of these from the permanent cliffs above: nothing about the structure is left in a bad
shape afterward. A resized array and a freshly-splayed tree are both now in better
shape than before the expensive operation, not worse — the cost was real, but it bought something,
rather than just being paid and gone the way a quicksort partition's wasted comparisons are.
AVL Tree closes the loop by removing the question
entirely. Its own opening paragraph states the guarantee plainly:
"for every node, the heights of its left and right
subtrees differ by at most 1... the height-balance guarantee turns back into a real
O(log n) bound on every operation, no matter what order the data
arrives in." Feed it the identical sorted sequence that collapses the plain Binary
Search Tree above into a straight line, and the rotations fire on every insert specifically to
prevent that shape from ever existing — there is no input, adversarial or lucky or unlucky, that
produces a worse bound than O(log n). Red-Black Tree makes the same hard promise with
a looser balance factor (cheaper rebalancing, a slightly taller tree in practice) — a different
constant, not a different category. This is the one bucket of the four where "worst case" and
"typical case" are the same claim, not merely close.
Treating "has a worst case" as one fact instead of answering both questions above.
A fixed-pivot Quicksort and a Skip List are both honestly described as "O(n²)" and
"O(n), worst case" respectively — but one of those worst cases is a design choice
away from being eliminated by randomization, and the other already is randomized and still
carries a (vanishingly small) residual risk. Naming the complexity class without naming which of
the four buckets above it falls into leaves out the part that actually decides whether to worry.
Assuming an amortized guarantee protects any specific call you're about to make.
It doesn't, and was never claimed to — Dynamic Array's own measured section above is explicit that
an individual resizing push is a real O(n) event, not a theoretical one. "Amortized
O(1)" is a true statement about a sum divided by a count, not a promise about the next line of
code specifically. A system with a hard real-time deadline on every single call needs the no-cliff
bucket's guarantee, not an amortized one, regardless of how good the amortized bound looks on
paper.
Assuming a randomized structure's "vanishingly unlikely" worst case means it can't be forced in an adversarial setting. It's a different risk than a permanent cliff, not zero risk — and the honest distinction only holds if the randomness is real and hidden from whoever supplies the input. A predictable or seeded-from-public-information source of randomness collapses the probabilistic-cliff bucket back into the permanent-cliff one, because an attacker who can predict the coin flips can choose an input that defeats them exactly as reliably as a fixed pivot does.