Online algorithm - Revision history

Karl Jones: /* See also */

2016-05-17T01:53:36Z

‎See also

Karl Jones: /* Performance */

2016-05-17T01:53:15Z

‎Performance

Karl Jones: Created page with "In computer science, an '''online algorithm''' is an algorithm that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input..."

2016-05-17T01:46:00Z

Created page with "In computer science, an '''online algorithm''' is an algorithm that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input..."

New page

In [[computer science]], an '''online algorithm''' is an [[algorithm]] 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.

== Example: Insert sort ==

The [[insertion sort]] algorithm considers one input element per iteration and produces a partial solution without considering future elements.

Thus, insertion sort is an online algorithm.

By contrast, [[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]].

== Performance ==

For many problems, online algorithms cannot match the performance of [[Offline algorithm|offline algorithms]].

If the [[ratio]] between the performance of an online algorithm and an optimal offline algorithm is [[bounded]], the online algorithm is called [[competitive]].

== Offline counterparts ==

Not every online algorithm has an offline counterpart.

== See also ==

* [[Algorithm]]
* [[Computer science]]
* [[Offline algorithm]]
* [[Ukkonen's algorithm]] - online algorithm for constructing [[Suffix tree|suffix trees]], proposed by [[Esko Ukkonen]] in 1995

== External links ==

* [https://en.wikipedia.org/wiki/Online_algorithm Ukkonen's algorithm] @ Wikipedia

[[Category:Algorithms]]
[[Category:Computer science]]

@@ Line 24: / Line 24: @@
 * [[Algorithm]]
 * [[Computer science]]
 * [[Offline algorithm]]

@@ Line 15: / Line 15: @@
 For many problems, online algorithms cannot match the performance of [[Offline algorithm|offline algorithms]].
-If the [[ratio]] between the performance of an online algorithm and an optimal offline algorithm is [[bounded]], the online algorithm is called [[competitive]].
+If the [[ratio]] between the performance of an online algorithm and an optimal offline algorithm is [[bounded]], the online algorithm is called [[Competitive analysis (online algorithm)|competitive]].
 == Offline counterparts ==