## 5 A Lower Bound  
**Theorem 3**.: _For any positive constant \(\varepsilon\), there is no \((2-\varepsilon)\)-competitive online algorithm for the online OVSF code assignment problem._  
Proof.: Consider an OVSF code tree of height \(h\) (where \(h\) is even), namely, the number of leaves are \(n=2^{h}\). First, an adversary gives \(n\) insertions of level-0 codes so that the vertices of level 0 are fully assigned, by which, an arbitrary online algorithm incurs the cost of \(n\). Then, depending on the assignment of the online algorithm, the adversary requires to remove one code from each subtree rooted at a vertex of level \(h/2\). (Hereafter, we simply say \"subtree\" to mean a subtree of this size.) Since there are \(\sqrt{n}\) such subtrees, the adversary gives \(\sqrt{n}\) deletions in total. Next, the adversary gives an insertion \(i_{c_{1}}\) of a level-\(h/2\) code. To assign \(c_{1}\), the online algorithm has to make one of subtrees empty by reassignments, for which the cost of at least \(\sqrt{n}-1\) is required.  
Again, depending on the behavior of the online algorithm, the adversary requires to remove \(\sqrt{n}\) codes of level 0 _uniformly_ from each subtree except for the subtree to which \(c_{1}\) is assigned. Here, \"uniformly\" means that the numbers of removed codes for any pair of subtrees differ by at most 1; in the current case, the adversary requires to remove two codes from one subtree, and one code from each of the other \(\sqrt{n}-2\) subtrees. Subsequently, the adversary gives an insertion \(i_{c_{2}}\) of a level-\(h/2\) code. Similarly as above, the online algorithm requires at least \(\sqrt{n}-2\) reassignments to assign \(c_{2}\).  
The adversary repeats the same operation \(\sqrt{n}\) rounds, where one round consists of \(\sqrt{n}\) deletions to remove codes of level 0 uniformly from subtrees, and one insertion of a level-\(h/2\) code. Eventually, all initial codes of level 0 are removed, and the final OVSF code tree contains \(\sqrt{n}\) codes of level \(h/2\).  
The total cost of the online algorithm is at least  
\[n+\sqrt{n}+\sum_{i=1}^{\sqrt{n}}(\sqrt{n}-\lceil\frac{\sqrt{n}} {\sqrt{n}+1-i}\rceil) = n+\sqrt{n}+\sum_{i=1}^{\sqrt{n}}(\sqrt{n}-\lceil\frac{\sqrt{n}} {i}\rceil)\] \[= 2n+\sqrt{n}-\sum_{i=1}^{\sqrt{n}}\lceil\frac{\sqrt{n}}{i}\rceil\] \[> 2n+\sqrt{n}-\sum_{i=1}^{\sqrt{n}}(\frac{\sqrt{n}}{i}+1)\] \[= 2n-\sum_{i=1}^{\sqrt{n}}\frac{\sqrt{n}}{i}\] \[= 2n-\sqrt{n}(\log\sqrt{n}+(\sum_{i=1}^{\sqrt{n}}\frac{1}{i}-\log \sqrt{n})).\]On the other hand, the cost of an optimal offline algorithm is \(n+\sqrt{n}\) since it does not need reassignment. Hence, the competitive ratio is at least  
\[\frac{2n-\sqrt{n}(\log\sqrt{n}+(\sum_{i=1}^{\sqrt{n}}\frac{1}{i}- \log\sqrt{n}))}{n+\sqrt{n}} = 2-\frac{\sqrt{n}(\log\sqrt{n}+2+(\sum_{i=1}^{\sqrt{n}}\frac{1}{i} -\log\sqrt{n}))}{n+\sqrt{n}}.\]  
Since \(\lim_{n\rightarrow\infty}(\sum_{i=1}^{\sqrt{n}}\frac{1}{i}-\log\sqrt{n})=\gamma\) (\(\gamma\simeq 0.577\)) is the Euler's constant, the term \(\frac{\sqrt{n}(\log\sqrt{n}+2+(\sum_{i=1}^{\sqrt{n}}\frac{1}{i}-\log\sqrt{n})) }{n+\sqrt{n}}\) becomes smaller than any positive constant \(\varepsilon\) as \(n\) goes infinity.