# Determining the space complexity of van Emde Boas trees

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 $$2^{2^k}$$.

It's easy to get the recurrence $$S(u^2) = (1+u) S(u) + \Theta(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 (and others) 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 another one in order to reach space complexity $$O(u)$$, while maintaining 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. (ZBL1187.68679) leaves it as an exercise.

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

1. van Emde Boas, P.; Kaas, R.; Zijlstra, E., Design and implementation of an efficient priority queue, Math. Syst. Theory 10(1976), 99–127 (1977). ZBL0363.60104.

2. van Emde Boas, P., Preserving order in a forest in less than logarithmic time and linear space, Inf. Process. Lett. 6, 80–82 (1977). ZBL0364.68053.

• 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! Oct 24, 2009 at 7:05
• Great advice, thank you! (here tough I'm happy I got a quick and excellent answer, but for the next time) Oct 24, 2009 at 7:36
• 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 Oct 17, 2010 at 6:25

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! Oct 24, 2009 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, 2009 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$? May 24, 2011 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? May 24, 2011 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