Problem Detail: 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 ?
Asked By : Geek
Answered By : A.Schulz
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6193 Ask a Question Download Related Notes/Documents
