an online algorithm

Picture a parking attendant who must wave each arriving car into a spot the moment it pulls up — she cannot wait to see how many cars will come, or how big they are, before deciding. Every choice is final and is made with only the past and present in hand, never the future. An online algorithm works exactly like this: the input arrives one piece at a time, and the algorithm must commit to an action on each piece before the next one is revealed. This is the opposite of an offline algorithm, which gets the entire input up front and may study all of it before doing anything.

More precisely, the input is a sequence of requests r1, r2, r3, ... revealed one by one. When request r_t arrives, the algorithm must produce its response for r_t using only r1..r_t (and its own past responses), and that response cannot be undone later. Consider a simple online task: you run a coat-check and must decide, as each guest leaves, whether to keep the line open one more minute or close it — once closed you cannot reopen. Because the algorithm is blind to what comes next, it can be forced into choices that look fine now but turn out badly once the rest of the sequence appears. That is the essential difficulty: not lack of cleverness, but lack of information.

Online algorithms matter because enormous parts of real computing are online: a cache must evict a page before knowing what is requested next; a router forwards a packet before seeing the rest of the traffic; an investor buys or sells before tomorrow's price. We cannot measure such an algorithm only against its own worst case, because some difficulty is unavoidable — so instead we compare it to the best possible offline solution that knew the whole future. That comparison is the competitive ratio. The honest caveat: 'online' does not mean 'on the internet' here; it means decisions are made incrementally, irrevocably, without the future.