LRU is k-competitive for the paging problem. Let k be the size of the cache. Theorem 1: LRU is k-competitive. Proof: Let Opt be the optimal offline algorithm. (N.B.: we do not have to assume that Opt is LFD.) We assume that the initial cache is given. (This is a standard assumption of the problem.) Let rho be the request sequence. Partition rho into "phases." The definition of a phase is that Opt faults on the first request of each phase, but does not fault on any other request of that phase. Thus, the total cost of Opt is the number of phases. Claim 1: For any given phase, let K be the set of pages in Opt's cache after the first request of that phase. Then all requests of that phase are to members of K. Proof of Claim: Any request outside K would cause Opt to fault, contradicting the assumption that Opt does not fault after the first request of the phase. Claim 2: If a page p is requested during a phase, LRU will not eject p during the remainder of that phase. Proof: suppose that page q is the i^th request of the phase, and that Q is the set of all pages requested in the first i requests of the phase. Since the cardinality of Q is at most k, and since each member of Q has been requested more recently than any page not in Q, LRU will not eject any member of Q when q is requested. Claim 3: For any given phase, let K be the set described above. Then, after LRU has faulted i times during that phase, LRU's cache contains at least i members of K. Proof: After i faults, LRU has brought i members of K into its cache. By Claim 2, none of these have been later ejected, so they are still there after i requests. Claim 4: LRU faults at most k times during any phase. Proof: Since K has only k members, Claim 3 shows that LRU cannot fault more than k times during the phase. We now complete the proof of Theorem 1. Let N be the number of phases. By definition, Opt pays N. By Claim 4, LRU pays at most Nk.