# 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

## 1 Answer

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.

• What exactly you mean by "relevant bits" ?Why did you put special emphasis on the word "relevant" ? – Geek Oct 20 '12 at 15:43
• The subproblem you solve has only a universum, with half of the size bitwise. I said "relevant", because I did not formally define what I mean by relevant, but it should be clear if you know vEB-trees. – A.Schulz Oct 20 '12 at 16:41