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 ?

  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ What exactly you mean by "relevant bits" ?Why did you put special emphasis on the word "relevant" ? $\endgroup$ – Geek Oct 20 '12 at 15:43
  • $\begingroup$ 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. $\endgroup$ – A.Schulz Oct 20 '12 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.