Online algorithm and competitive analysis

Summary

An online algorithm receives its input one piece at a time and must act on each piece before it sees the next one. Competitive analysis measures such an algorithm by comparing its cost with the cost of an optimal offline algorithm that knows the whole input in advance. The worst ratio of the two costs, over all inputs, is the competitive ratio. Standard examples are paging, where the least-recently-used rule is $k$-competitive for a cache of $k$ pages, and the ski rental problem.