A new rule of the game: the future is hidden
Every algorithm you have studied so far shared one quiet luxury: the entire input was sitting in front of it before it made a single move. Merge sort saw the whole array; Dijkstra saw the whole graph; even a hard problem like knapsack at least knew all the items up front. This rung throws that luxury away. An online algorithm receives its input one piece at a time, and must respond to each piece — irrevocably — before the next one arrives. It is not allowed to wait, peek ahead, or undo. The future is genuinely hidden, and decisions are final.
This is not an artificial constraint invented to make life hard — it is the everyday situation of real systems. A cache decides what to evict before knowing which page is requested next. A ride-hailing service must dispatch a car to a rider now, not after the night's requests are all known. A router forwards a packet without seeing tomorrow's traffic. In each case waiting for the full input is impossible, because the input is the future. So we need a way to design algorithms that decide blindly, and — harder — a fair way to judge how good a blind decision-maker can possibly be.
The yardstick: competing against a clairvoyant
How do you grade an algorithm that is doomed to make some mistakes simply because it cannot see the future? Comparing its cost to zero is unfair; comparing it to another online algorithm tells you little. The clean idea, and the heart of this whole rung, is to compare it against the optimal offline algorithm — an imaginary opponent, usually called OPT, who is handed the entire input sequence in advance and plays it perfectly. OPT is a clairvoyant: it is not a real algorithm you could run, it is the gold standard of hindsight. Our online algorithm must play blind; OPT plays with the whole script in hand.
The competitive ratio is the number that records the gap. For a minimization problem (paying a cost, like cache misses or dollars), an online algorithm ALG is c-competitive if for every input sequence, cost(ALG) <= c times cost(OPT) + b, where b is a fixed constant that does not grow with the input. The additive b absorbs small startup effects; the multiplicative c is what we really care about. A 2-competitive algorithm promises: no matter what the future throws at me, I never pay more than twice what an all-knowing planner would have paid. That promise holds for every sequence — it is a worst-case guarantee, in exactly the spirit of the approximation ratio from the previous rung, with OPT-with-hindsight playing the role the unknown optimum played there.
Ski rental: the smallest honest example
The cleanest place to feel competitive analysis is the ski rental problem. You are skiing, but you do not know how many more days you will ski — it could be one, it could be the whole season. Each day you can rent skis for $1, or at any point buy them outright for $B (say $10) and ski free forever after. If you knew the total number of days in advance, the choice would be trivial: ski fewer than B days, rent the whole time; ski B or more days, buy on day one. But you do not know — each morning you must decide rent-or-buy with the future hidden. This is rent-or-buy in miniature, and it appears everywhere: keep paying a small recurring cost, or pay once to make it go away.
Here is the famous strategy: rent for the first B-1 days, and if you are still skiing on day B, buy. Watch it against OPT. If the season turns out short — you stop after k < B days — you spent k dollars renting, and OPT (knowing k) would also have rented for k, so you tied. If the season is long — you ski at least B days — you paid B-1 dollars renting plus B to buy, a total of 2B-1; but OPT, knowing the season was long, would have bought on day one for exactly B. The ratio is (2B-1)/B = 2 - 1/B, just under 2. So this simple rule is (2 - 1/B)-competitive: you never pay more than essentially twice what a clairvoyant would.
rent-until-break-even (buy price = B):
days_rented = 0
while you are still skiing today:
if days_rented == B-1:
buy ($B), ski free forever # break-even reached
else:
rent today ($1); days_rented += 1
worst case total = (B-1) + B = 2B-1 , OPT = B -> ratio 2 - 1/BWhy not buy earlier, or later? An adversary argument pins it down. Suppose your rule is "buy on day m." The adversary, knowing m, simply makes you stop skiing the day after you buy: you wasted the purchase. Buy too early (small m) and a short season catches you having bought skis you barely used; buy too late (large m) and a long season catches you having rented far past the break-even point. The break-even choice m = B is the unique balance point that makes both traps cost the same factor, and no deterministic rule can do better than 2 - 1/B. That last sentence is a genuine lower bound, not a failure of imagination — the adversary provably defeats every deterministic strategy by at least this much.
Paging: the same idea at the heart of every cache
Ski rental is a toy, but the same machinery governs a problem inside every computer: paging. A cache holds k pages of fast memory; requests for pages arrive one at a time; a request for a page already in the cache is free (a hit), but a request for a missing page is a fault and forces you to load it, evicting some page to make room. Which one do you evict? You must choose now, without seeing the future request stream. The cost we count is the number of faults, and we ask: how close to the unavoidable minimum can an online eviction rule stay?
The offline optimum here is a beautiful clairvoyant rule called Belady's algorithm: always evict the page whose next use is furthest in the future. It is provably optimal — but unrunnable online, because it reads the future. Real caches use rules like LRU (evict the least-recently-used page) or FIFO. The striking theorem is that LRU and FIFO are each exactly k-competitive: on the worst sequence they fault up to k times as often as Belady, where k is the cache size, and no deterministic online paging rule can beat k. So a 1000-slot cache can in the worst case fault 1000 times more than hindsight would — sobering, yet this is the best achievable deterministic guarantee, and on real traces with locality LRU usually performs far better than this ceiling.
The lower-bound half is again an adversary argument, and it is worth seeing the shape. Restrict attention to k+1 distinct pages — one more than fits in the cache. Whatever deterministic rule the online algorithm uses, the adversary, knowing the rule, always requests the one page the algorithm just evicted. Every single request is then a fault: k+1 requests, k+1 faults, in the long run a fault on essentially every step. Meanwhile Belady, holding all but the page used furthest ahead, faults only about once every k requests on that same sequence. Divide and you get the factor k. The adversary never needs more than k+1 pages to expose the worst case — a tiny, exact construction, exactly like the matching that lower-bounded vertex cover.
Randomness breaks the adversary's grip
Those lower bounds — 2 - 1/B for ski rental, k for paging — feel like walls. But they are walls only for deterministic algorithms, because the adversary's whole power comes from predicting exactly what you will do. The moment your algorithm flips coins, the adversary loses that certainty: it can still choose the input, but it can no longer know which page you will evict or which day you will buy. This is the same lever that made randomized quicksort robust against the sorted-input attack — randomness denies the adversary a fixed target. Against an oblivious adversary (one who fixes the whole sequence in advance, not adapting to your coin flips), randomization can lower the competitive ratio dramatically.
For ski rental, a randomized buy-day (choosing when to buy from a carefully skewed probability distribution rather than fixing day B) brings the expected competitive ratio down from 2 to e/(e-1), about 1.58 — a real improvement, proven not by luck but by averaging the cost over the coin flips. For paging, the randomized marking algorithm achieves an expected ratio of about 2 ln k instead of k: for k = 1000 that is roughly 14 instead of 1000, an enormous gap. The honesty caveat matches the one for randomized quicksort: these improved ratios are expectations over the algorithm's internal randomness. On any single run you might do worse; what is guaranteed is the average over the coins, for every fixed input the oblivious adversary can pick.
Where this sits, and where the rung goes next
Step back and see the unifying picture. Competitive analysis is, in spirit, the same move you have made again and again: pin an unknowable quantity against a computable surrogate. In approximation it was OPT trapped by a cheap lower bound; here it is the future trapped by comparison with a clairvoyant who already saw it. Each frontier in this rung relaxes a different assumption you once took for granted. Online algorithms drop the assumption that you see the whole input before deciding. The next guides drop others: that you can store the whole input, that worst-case is the only honest lens, that exponential time is the only price for hard structure.
- Guide 2 drops the storage assumption: the streaming model, where data rushes past once and memory is far too small to keep it — and sketches let you answer questions anyway with provably tiny space.
- Guide 3 attacks hardness by structure: parameterized complexity and FPT, where an NP-hard problem becomes tractable once you isolate a small parameter and confine the exponential blow-up to it alone.
- Guide 4 turns to practice when proofs run out: local search and metaheuristics — simulated annealing and friends — that climb toward good solutions with no competitive guarantee but real-world muscle.
- Guide 5 questions the worst case itself: smoothed analysis explains why algorithms feared in theory thrive in practice, by perturbing the adversary's input just slightly.
Carry one habit out of this guide and it will serve you through the rest of the rung: whenever an algorithm must act under a handicap — no future, no memory, no time — first name the all-powerful opponent it is being measured against, then find the simple adversary construction that caps how well anyone can do. Ski rental's break-even day and paging's k+1 pages are not isolated tricks; they are the same honest accounting, applied wherever ignorance has a price.