You are skiing for an unknown number of days. Each morning you either rent skis for 1, or buy a pair for B and ski free forever after. Every evening the season might end — and nobody tells you in advance. Rent too long and you overpay; buy too early and the season ends tomorrow. How much does not knowing the future cost you?
ALG is c-competitive if, on every input σ, it stays within a factor
c of what a clairvoyant offline optimum would have paid:d, and the optimum in hindsight is trivial:
OPT(d) = min(d, B) — rent all season if it is short, buy on day 1 if it is long. The whole
difficulty is that d is revealed only as it happens.Why 2 − 1/B. Rent on days 1…B−1, buy on day B. If the season ends before day B you paid exactly what OPT
paid — ratio 1. Otherwise you paid (B−1) + B = 2B−1 while OPT paid B, giving
(2B−1)/B = 2 − 1/B. The worst case lands precisely on day B: one day earlier and the extra rental
day has not happened yet, one day later and OPT stops growing while you have already stopped paying.
Nothing deterministic does better. An adversary that ends the season the moment you buy forces the ratio
above; the curve shows every other buy-day j is worse. Randomizing the buy day defeats that adversary — it can no
longer aim at a day it cannot predict — and brings the expected ratio down to e/(e−1) ≈ 1.58.
OPT here is the optimum for a season ending today, i.e. min(day, B), so the ratio
shown at each step is the honest one. Ski rental is the seed of a whole family — TCP acknowledgement delay,
snoopy caching, spinning-vs-blocking locks are all rent-or-buy in disguise.