An online algorithm must act on incoming items of information without any knowledge of future inputs. For example, a cache replacement protocol must decide which cache block to remove when the cache is full without knowing which memory blocks will be accessed in the future. The quality of an online algorithm is measured relative to the best possible performance of an adversary that has complete knowledge about the input sequence. Such an analysis is call a competitive analysis.