online algorithm (thing)

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:

• Finding connected components is an offline problem. You are given a graph (say as a list of edges), and must group vertices into connected components. This can be solved by matrix multiplication -- raise the adjacency matrix of the graph to a high power (the number of vertices is high enough). For some graphs, dynamic programming (e.g. Djikstra's algorithm or similar) gives much better performance.

  The online version of the problem is the union find problem. You start with n disconnected vertices. Inputs are either requests to add an edge between two vertices, or a query for the (current) identifier of the connected component to which a vertex belongs. Tarjan's union find with path compression algorithm gives excellent performance even for this online version.

• Sorting for the purpose of efficient searching is another offline problem. You are given as input a list of elements and produce as output a sorted list. You pay time O(n log n) to sort the list, and another O(log n) time every time you wish to search for an element. Any search algorithm will do; merge sort, quick sort and heap sort are all good, simple choices.

  The online version of this algorithm requires you to be able to search for elements before you have seen them all. This is precisely the problem which balanced trees solve for you! By storing incoming elements in a tree (such as an AVL tree, a red-black tree or a B-Tree), you pay O(log n) time to add each element and still only O(log n) to search for an element.