Editing Online algorithm (section)

{{Short description|Algorithm that begins on possibly incomplete inputs}}
{{distinguish|online and offline}}

In [[computer science]], an '''online algorithm'''<ref name="karp92" /> 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. 

In [[operations research]], the area in which online algorithms are developed is called [[online optimization]].

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. 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]].<ref name=karp92>{{cite journal|last1=Karp|first1=Richard M.|title=On-line algorithms versus off-line algorithms: How much is it worth to know the future?|journal=IFIP Congress (1)|date=1992|volume=12|pages=416–429|url=http://www.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf|access-date=17 August 2015}}</ref>

Not every ''offline algorithm'' has an efficient ''online'' counterpart.

In grammar theory they are associated with [[Straight-line grammar]]s.