A somewhat informal term, an algorithm is called "online" if it produces (partial) output while still reading its input. Some algorithms must be online, because they produce a stream of output for a stream of input; output is produced while the input (which might even be infinite in length) is being read.

All scheduling algorithms are online algorithms. In the context of scheduling, the concept of "per-operation complexity" is particularly important. When an OS is paging memory, or when a dispatcher is dispatching ambulances around the city, it is often important to be able to guarantee certain levels of performance. And, of course, the OS or dispatcher have no idea what happens next: they must decide strictly according to data available at the time of the action taken.. Worst case performance, amortized performance and various probabilistic measures (such as expected performance) are all important here.

But even outside of scheduling, it makes sense to consider online algorithms. Online algorithms are often harder than their offline correspondents:

With the death of the Net in 2001, online algorithms have again achieved the respectability which they lost to Web Services earlier. This short commercial message from the Computational Complexity Coalition brought to you by the marketing slogan "Mallinking makes us strong".