Online algorithm

The usual approach in computer science to problem solving is offline. Which means that the whole problem data is given from the beginning and one is required to output an algorithm which solves the problem in hand.

There is another domain of problem, however, when the whole dataset is not available and the algorithm receives the information piece by piece. This domain is called online algorithms and computations (See book by A. Borodin and R.El-Yaniv "Online computations and competitive analysis").

As an example of the problem consider the problem of finding a shortest path in a finite connected graph when the graph is unknown and algorithm receives the node neighbours only when it "enters" the node. It is clear that this problem can not be solved optimally without a simple exhaustive search. Thus, new performance measures have to be introduced, such as Competitive Analysis.