# Size of the universe for van Emde Boas Trees

In order to achieve the time complexity of $O(\log \log u)$ for van Emde Boas trees I read in this lecture that the the universe size $u$ is chosen as $u = 2^{2^k}$ for some integer $k$ for van Emde Boas trees. Why choose $u$ to be of this specific form ?

• There's also a standard hand-wave in this kind of analysis. If the universe is not exactly that size, you can pad it to the next larger $k$ without affecting the asymptotic run-time. – Joe Oct 22 '12 at 20:07

This assumption makes the analysis easier. If the universe $\mathcal{U}$ is of size $2^{2^k}$ then every element in $\mathcal{U}$ can be represented by $2^k$ bits. Roughly speaking, when executing one of the vEB-tree operations you halve the "relevant bits" in every level of the recursion. So when you start with $2^k$ bits, then the recursion depth is $k$.
If your universe has a size not of the form $2^{2^k}$, then you have to use floor/ceiling in the analysis.