## 4 Competitive Analyses of Extended-Lazy  
First, we estimate the cost and the increase in the number of locally rich levels incurred by applications of Repair. By a single application of Repair, the cost of 1 is incurred and the number of locally rich levels increases or decreases by one. In case that the number of locally rich levels increases by one, the resulting OVSF code tree is semi-compact. On the other hand, if the number of locally rich levels decreases by one, the resulting OVSF code tree may not be semi-compact and we may need one more application of Repair. Hence, if Repair is executed \(k\) times, then the total cost of \(k\) is incurred, and the number of locally rich levels decreases by \(k-2\) or \(k\). (In the case of \(k=1\), \"decreases by \(k-2\)\" means \"increases by one\".) Then, we estimate the cost and the increase in the number of locally rich levels for each of the cases (1) through (6) and (I) through (VIII) of Extended-Lazy. From the observations of Sects. 3.1. and 3.2., and the above observation on Repair, these quantities can be calculated as in Table 1. There are two values in Case (5): Left and right values correspond to the cases where Cases (2) and (3), respectively, are executed after Case (5). There are also two values in Cases (III), (VII), and (VIII) corresponding to behaviors of Extended-Lazy. In the lower table, \(k\) denotes the number of applications of Repair. One can see that, from the upper table, the sum of the cost and the increase in the number of locally rich levels is at most 4 for serving an insertion. This occurs when Extended-Lazy executes Case (5) followed by Case (3). Similarly, by the lower table, the sum of the cost and the increase in the number of locally rich levels for serving one deletion is at most 3, which occurs in Cases (III), (IV), (VII), and (VIII). Now, we are ready to calculate the competitive ratio of Extended-Lazy. For an arbitrary input sequence \(\sigma\), let \(I\) and \(D\) be the sets of insertions and deletions in \(\sigma\), respectively. It is easy to see that the cost of an optimal offline algorithm is at least \(|I|\) because each insertion incurs a cost of 1 in any algorithm. We then estimate the cost of Extended-Lazy. For \(i\in I\) and \(d\in D\), let \(e_{i}\) and \(e_{d}\) be the costs of Extended-Lazy for serving \(i\) and \(d\), respectively. The cost of Extended-Lazy for \(\sigma\) is then \(\sum_{i\in I}e_{i}+\sum_{d\in D}e_{d}\). Also, for \(i\in I\) and \(d\in D\), let \(q_{i}\) and \(q_{d}\) be the increases in the number of locally rich levels caused by Extended-Lazy in serving \(i\) and \(d\), respectively. Define \(Q\) to be the number of locally rich levels in the OVSF code tree at the end of the sequence \(\sigma\). Then, \begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|} \cline{2-10} \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Case} & \multicolumn{1}{c|}{(1)} & \multicolumn{1}{c|}{(2)} & \multicolumn{1}{c|}{(3)} & \multicolumn{1}{c|}{(4)} & \multicolumn{1}{c|}{(5)} & \multicolumn{1}{c|}{(6)} \\ \cline{2-10} \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Cost} & 1 & 1 & 3 & 2 & 2 & 4 & 3 \\ \cline{2-10} \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{Increase} & \(\leq 1\) & \(\leq 1\) & \(0\) & \(\leq 1\) & \(\leq 1\) & \(0\) & \(0\) \\ \hline \end{tabular}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \cline{2-10} \multicolumn{1}{c|}{} & \multicolumn{1}{c|}{(II)} & \multicolumn{1}{c|}{(III)} & \multicolumn{1}{c|}{(IV)} & \multicolumn{1}{c|}{(V)} & \multicolumn{1}{c|}{(VI)} & \multicolumn{1}{c|}{(VIII)} \\ \hline \multicolumn{1}{c|}{Cost} & \(\leq k+1\) & \(\leq 1\) & \(k+1\) & \(k+2\) & \(\leq 2\) & \(\leq k+1\) & \(\leq 1\) & \(k+1\) & \(k+2\) & \(1\) & \(2\) \\ \hline \multicolumn{1}{c|}{Increase} & \(\leq-k+1\) & \(\leq 1\) & \(\leq-k+2\) & \(\leq-k+1\) & \(1\) & \(\leq-k+1\) & \(1\) & \(\leq-k+2\) & \(\leq-k+1\) & \(\leq 2\) & \(1\) \\ \hline \end{tabular}
\end{table} 
Table 1: The costs and increases in the number of locally rich levels for each execution of Extended-Lazy. since there is no locally rich level at the beginning.