display | more...

Really only used in contrast to online algorithm, as much of computer science routinely does not even consider online algorithms. Whereas an online algorithm is required to give various outputs during an input stream, it is frequently measured against the optimal algorithm to solve the "offline version" of the same problem. In competitive analysis, one tries to construct an online algorithm that is only worse than the offline algorithm by at most some (preferably small) constant.

In fact, the "offline" algorithm is more of an "omniscient" algorithm, since a possibly infinite input stream may never really be considered offline. The optimal offline algorithm is simply assumed always to choose the optimal input (such that the end result is optimal).

This approach stems from the same considerations as the worst case or adversarial model ubiquitous in complexity theory.

Log in or register to write something here or to contact authors.