An online algorithm will never be better than the corresponding offline or "omniscient" algorithm -- an algorithm faced with the same problem, which for any input stream "guesses" the optimal output at every step. This is because at the very least the offline version could simulate having to return output prematurely, given partial input. But how to measure the (decreased) performance of an online algorithm?

Sometimes, a probabilistic model of the input is available, and the goal is to minimise the expected cost (or maximise the expected return, or whatever you measure the offline version by). But what if you have no probabilistic model?

The answer recently popular in computer science is "competitive analysis": an online algorithm is said to be c-competitive, if it is never more than c times as bad as the best (optimal) offline version. If you lack a probabilistic model, this is a good estimate, in line with the worst case or "adverserial" model favoured in much of computer science. The smaller your c, the better. A typical goal of computer scientists in this field is to find a c-competitive online algorithm, and prove that c to be the best possible. (But note that sometimes, there is no c-competitive solution at all, for any c!)

The absolute standard introductory online algorithm problem is the Ski Rental Problem: you're on your first-ever ski holiday, and you have no idea how many times you'll want to go skiing; every morning you must decide, should you buy your own skis (for $150) or rent them for one day (for $10)? (Your goal is to minimise total expenditure). The answer, although simple, gives a feel for some of the field's quirks and surprises. But give the problem description a go before you head for the spoiler.

Here are two other instructive problems in similar vein. Consider them at your leisure...

  1. You've lost your spectacles somewhere along the beach, right by the water. As a result, you can only actually see them if you're right next to them. They could be anywhere along the beach (which stretches north and south, infinitely). What path should you take along your search, to minimise the total distance walked? (The optimal algorithm, given the actual location of the spectacles, is trivial).
  2. You are offered a succession of predetermined (but unknown to you) cash prizes. When each sum is offered, you may take the prize (ending the game), or decline it and proceed to the next offer. What strategy should you adopt?

In the real world™, online algorithms are often considered in the context (or pretext?) of load balancing problems, where a resource or resources must be allocated to (dependent or independent) tasks of varying cost and profitability. These have applications in communications and other lucrative businesses. The simpler scenarios are well studied, but many important problems are still open.