Online algorithm
Definition
Definition
----------

Because it does not know the whole input, an online algorithm is forced to make decisions that may later turn out not to be optimal, and the study of online algorithms has focused on the quality of decision\-making that is possible in this setting. [Competitive analysis](/wiki/Competitive_analysis_%28online_algorithm%29 "Competitive analysis (online algorithm)") formalizes this idea by comparing the relative performance of an online and offline algorithm for the same problem instance. Specifically, the competitive ratio of an algorithm, is defined as the worst\-case ratio of its cost divided by the optimal cost, over all possible inputs. The competitive ratio of an online problem is the best competitive ratio achieved by an online algorithm. Intuitively, the competitive ratio of an algorithm gives a measure on the quality of solutions produced by this algorithm, while the competitive ratio of a problem shows the importance of knowing the future for this problem.

### Other interpretations

For other points of view on *online inputs to algorithms*, see 
* [streaming algorithm](/wiki/Streaming_algorithm "Streaming algorithm"): focusing on the amount of memory needed to accurately represent past inputs;
* [dynamic algorithm](/wiki/Dynamic_algorithm "Dynamic algorithm"): focusing on the time complexity of maintaining solutions to problems with online inputs.

### Examples

Some *online algorithms*:
* [Insertion sort](/wiki/Insertion_sort "Insertion sort")
* [Perceptron](/wiki/Perceptron "Perceptron")
* [Reservoir sampling](/wiki/Reservoir_sampling "Reservoir sampling")
* [Greedy algorithm](/wiki/Greedy_algorithm "Greedy algorithm")
* [Adversary model](/wiki/Adversary_%28online_algorithm%29 "Adversary (online algorithm)")
* [Metrical task systems](/wiki/Metrical_task_systems "Metrical task systems")
* [Odds algorithm](/wiki/Odds_algorithm "Odds algorithm")
* [Page replacement algorithm](/wiki/Page_replacement_algorithm "Page replacement algorithm")
* [Algorithms for calculating variance](/wiki/Algorithms_for_calculating_variance "Algorithms for calculating variance")
* [Ukkonen's algorithm](/wiki/Ukkonen%27s_algorithm "Ukkonen's algorithm")


How do different types of online algorithms, such as streaming or dynamic ones, relate to each other?