In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.
In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand.
As an example, consider the sorting algorithms selection sort and insertion sort: selection sort repeatedly selects the minimum element from the unsorted remainder and places it at the front, which requires access to the entire input; it is thus an offline algorithm. On the other hand, insertion sort considers one input element per iteration and produces a partial solution without considering future elements. Thus insertion sort is an online algorithm.
Note that the final result of an insertion sort is optimum, i.e., a correctly sorted list. For many problems, online algorithms cannot match the performance of offline algorithms.
Not every offline algorithm has an efficient online counterpart.
Arithmetic Mean
In mathematics and statistics, the arithmetic mean or simply the mean, is the sum of a collection of numbers divided by the count of numbers in the collection. The collection is often a set of results of an experiment or an observational study, or frequently a set of results from a survey.
Naive formula:
Donald Knuth, who is considered the father of computer science, pointed out that the online algorithm is always the best way to compute the arithmetic mean.
Knuth’s formula:
The intuition under Knuth’s formula (the one above) was to “adjust” the mean value as a new observation arrives, to make the mean value converges to its proper value.
Leave a Reply
Want to join the discussion?Feel free to contribute!