3
$\begingroup$

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 ?

$\endgroup$
1
  • $\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, 2012 at 20:07

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What exactly you mean by "relevant bits" ?Why did you put special emphasis on the word "relevant" ? $\endgroup$
    – Geek
    Oct 20, 2012 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, 2012 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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