## 4 Competitive Analyses of Extended-Lazy
The cost of Extended-Lazy for \(\sigma\) is  
\[\sum_{i\in I}e_{i}+\sum_{d\in D}e_{d} \leq \sum_{i\in I}e_{i}+\sum_{d\in D}e_{d}+Q \tag{1}\] \[= \sum_{i\in I}(e_{i}+q_{i})+\sum_{d\in D}(e_{d}+q_{d})\] \[\leq \sum_{i\in I}4+\sum_{d\in D}3\] \[= 4|I|+3|D|\] \[\leq 7|I|. \tag{2}\]  
(1) is due to the above analysis, and (2) is due to the fact that \(|D|\leq|I|\) since for each deletion, there must be a preceding insertion corresponding to it. Now, the following theorem is immediate from the above inequality. **Theorem 1**. : _The competitive ratio of Extended-Lazy is at most 7._  
Next, we give a lower bound on the competitive ratio of Extended-Lazy. **Theorem 2**. : _The competitive ratio of Extended-Lazy is at least \(7-\varepsilon\) for any positive constant \(\varepsilon\)._  
Proof. : Consider an OVSF code tree of height \(h\) (\(h\geq 5\)). The number of leaves \(n\) is \(2^{h}\). First, we give following requests in this order (which we call the _initialization sequence_): \(n/4\) insertions of level-0 codes, an insertion of a level-1 code, an insertion of a level-0 code, an insertion of a level-\(i\) code for \(i=2,3,\ldots,h-2\) (\(h-3\) insertions in total), and an insertion of a level-2 code. Note that after the initialization sequence, two tanks (tank[0, 1] and tank[2, \(h-2\)]) are created at the \((n/4+2)\)-th and the final request, respectively. Extended-Lazy can serve each insertion with cost 1, thus the cost of Extended-Lazy is \(n/4+h\). Note that the cost of an optimal offline algorithm OPT is also \(n/4+h\). Next, we consider the _I-sequence_, which is defined as the sequence of \(h-4\) insertions of level-\(i\) codes for \(i=1,\ldots,h-4\) (in the increasing order of \(i\)). When the I-sequence is given to Extended-Lazy after the initialization sequence, Extended-Lazy executes Case (5) followed by Case (3) for every insertion in the I-sequence. We then define the _D-sequence_. It consists of the \(h-4\) deletions of level-\(i\) codes for \(i=h-4,\ldots,1\) (in the decreasing order of \(i\)). Here, each deletion requires to remove the code which is assigned to the leftmost vertex among all assigned vertices in the corresponding level. If the D-sequence is given to Extended-Lazy subsequently to the I-sequence, then Extended-Lazy executes Case (VIII) for each deletion in the D-sequence. Finally, we define the _T-sequence_ which consists of two requests; the former is a deletion of a level-\(2\) code, which requires to remove the code assigned to the leftmost assigned vertex of level 2, and the latter is an insertion of a level-\(2\) code. For each of the T-sequence, given after the D-sequence, Extended-Lazy executes Cases (I) and (2), respectively. It should be noted that, for Extended-Lazy, the configuration of the OVSF code tree at this moment is the same as the one immediately after processing the initialization sequence. The complete sequence is as follows: We first give the initialization sequence. Then, we repeat \(k\) times the concatenation of I-sequence, D-sequence, and T-sequence. Careful calculation shows that the cost of Extended-Lazy for each concatenation is \(k(7h-26)\), while the cost of an optimal offlinealgorithm OPT is \(k(h-3)\). Hence, the ratio between the costs of Extended-Lazy and OPT is \(\frac{n/4+h+k(7h-26)}{n/4+h+k(h-3)}=7-\frac{3n/2+6h+5k}{n/4+h+k(h-3)}\). Note that \(3n/2+6h+5k\) and \(n/4+h+k(h-3)\) are positive because \(h\geq 5\) and \(k>0\). Now, if \(h\) and \(k\) go infinity, \(\frac{3n/2+6h+5k}{n/4+h+k(h-3)}\) becomes smaller than any positive constant \(\varepsilon\).