Homework 19

Due Friday, April 24 at 7:00 PM. Please refer to the homework policy here.


  1. In the video, we showed that an LRU cache is -competitive w/r/t an optimal cache of the same size . Here we will go for a slightly different "bicriteria" bound. Let . Show that an LRU cache of size is -competitive with any optimal cache of size .

    That means, for example, that an LRU cache of size is 2-competive with any cache of size . Some people find this bound more compelling.

    You should be able to prove this by a short modification of the argument of the -competive bound. It suffices to point out just which part of the argument should change, and how.