the competitive ratio
How do you grade a decision-maker who is forced to act blind to the future? It seems unfair to compare her to a flawless oracle, yet we still want a number. The competitive ratio gives one: it measures how much worse an online algorithm does, in the worst case, than the best possible solution that knew the entire input in advance. It is the universally agreed scorecard for online algorithms, the way big-O is the scorecard for running time.
Precisely: let ALG(sigma) be the cost your online algorithm pays on input sequence sigma, and let OPT(sigma) be the smallest cost any offline algorithm — one that saw all of sigma up front — could pay on that same sigma. An algorithm is c-competitive if there is a constant c (and a fixed additive constant a) such that for EVERY sigma, ALG(sigma) <= c * OPT(sigma) + a. The competitive ratio is the smallest such c. The additive a lets us ignore tiny startup effects so we capture the long-run behavior. A ratio of 1 means you match the all-knowing optimum; a ratio of 2 means you might pay twice the unavoidable cost, but never more. The key move is that OPT, not your own best case, is the yardstick — so a large ratio honestly reflects the price of not knowing the future.
This idea is powerful because it is a worst-case guarantee that holds against an adversary who designs the input to hurt you, yet it never blames you for difficulty no real algorithm could avoid (OPT had the same input). It is also where the surprises live: paging's natural LRU rule is k-competitive, ski-rental's break-even strategy is 2-competitive, and these bounds are often provably the best any online method can achieve. The honest caveat: a competitive ratio is a worst-case measure over adversarial inputs, so a 2-competitive algorithm is not 'usually twice as bad' — on typical inputs it is often far better; the 2 is only the guaranteed ceiling.
Ski-rental: renting costs 1 per day, buying costs B once. The strategy 'rent for B-1 days, then buy on day B' is 2-competitive: against any number of ski days, you pay at most 2*OPT - 1. If you ski fewer than B days, buying was a waste, but you only rented; if you ski many days, you bought just one day 'late'. Either way you never exceed twice the cost of the future-knowing optimum.
c-competitive: ALG <= c*OPT + a on every input, with OPT the future-knowing optimum.
The competitive ratio compares against OPT (an all-knowing offline optimum), not against your own average case. So '2-competitive' is a worst-case ceiling, not a typical-case prediction; on benign inputs the algorithm is often near-optimal.