We call S(u) the space complexity of the vEB tree holding elements in the range 0 to u-1, and suppose without loss of generality that u is of the form 22k.

It's easy to get the recurrence S(u2) = (1+u) S(u) + Θ(u). (In Wikipedia's article the last term is O(1), but it's wrong because we must count the space for the array.)

Van Emde Boas gave in [1] the trivial bound S(u) = O(u log log u), and later in [2] he found a clever way to combine the data structure with other one so that to reach space complexity O(u), while mantaining the O(log log u) time bounds.

But modern references present the original data structure and state without proof that the space complexity is O(u). For instance, the very recent 3rd edition of "Introduction to algorithms" by Cormen et al. leaves it as an exercise.

I tried with some friends to [dis]prove the O(u) bound without luck.

[1] http://www.springerlink.com/content/h63507n460256241/

[2] http://www.cs.ust.hk/mjg_lib/Library/VAN77.PDF

  • This is a great instance of a question that could do with more background -- at very least give us links to good definitions, but hopefully some motivation too. You'll get more readers, and probably more upvotes on the question too! – Scott Morrison Oct 24 '09 at 7:05
  • Great advice, thank you! (here tough I'm happy I got a quick and excellent answer, but for the next time) – Diego de Estrada Oct 24 '09 at 7:36
  • 1
    It's not a direct answer to your question, so I'll just leave it in a comment, but you should read Mihai Pătraşcu's blog posts on vEB space: infoweekly.blogspot.com/2010/09/… and infoweekly.blogspot.com/2010/09/veb-space-method-4.html – David Eppstein Oct 17 '10 at 6:25
up vote 3 down vote accepted

The recurrence S(u2) = (1+u) S(u) + Θ(u) can be shown to be O(u) by the following method: First assume that the constant in the Θ(u) is at most 1 and that S(4) is at most 1, by dividing through as necessary.

Then we can prove S(u) < u - 2 by induction. The base case S(4) holds by the above assumption. The inductive case is

S(u^2) < (1+u) (u-2) + u = u2 - 2,

as desired.

Incidentally, I think one can avoid the Θ(u) term and have Θ(1) instead by not actually storing the array of pointers to substructures (as in the exposition currently on Wikipedia) but instead having implicit substructures all stored in one big array. Of course, some work would need to be done to show that you can keep track of all the necessary information. Either way, the solution above works.

  • I'm quite embarrased to know it was so easy. Thanks! – Diego de Estrada Oct 24 '09 at 6:58
  • The secret here is that I once had to solve a recurrence that seemed "obviously" linear, but no induction of the form f(x) < a*x+b worked unless b was sufficiently negative. Since then, I have remembered this possible approach. – aorq Oct 24 '09 at 7:04
  • How can you just "divide through as necessary"? Suppose, the recurrence is $S(u^2) = (1+u)S(u) + c_1u$ and $S(4) = c_2$, with $c_1 < c_2$. Then how can I just divide through by $c_2$? – Gabriel May 24 '11 at 13:13
  • Taking $S'(u)=S(u)/c_2$ leads to the recurrence $S'(u^2)=(1+u)S'(u)+(c_1/c_2)u$, where the $u$-term has constant $< 1$, and $S'(4)=1$. Where is the problem? – Emil Jeřábek May 24 '11 at 13:33

The van Emde Boas tree can be randomized to achieve $O(n)$ space usage instead of $O(u)$. For this purpose, we must replace the low-arrays by hash tables. But such modification occupies $O(n\log\log u)$ space. However if we use $\log u/2^i$ bits per hash table enty on $i$th level of recursion, the structure takes only $O(n)$ space. If a dynamic perfect hashing is used, the lookup queries still work in $O(\log\log u)$ worst-case time but insertions/deletions work in $O(\log\log u)$ expected amortized time.

See Mikhai Patrascu's blog for further explanation: http://infoweekly.blogspot.ru/2010/09/van-emde-boas-and-its-space-complexity.html

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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