## 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 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.

-
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 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) – Diego de Estrada 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/… – David Eppstein 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! – Diego de Estrada 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

This is intended as a comment, but I lack the MO reputation to leave comments.

Actually, I have a question regarding A.Rex's answer: 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$?

-
 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 2011 at 13:33

I have another question about the space complexity; I am putting it here, because I don't think it justifies a new, separate page in MathOverflow.

I am thinking of a variant of vEB trees. As you know, in the plain vEB tree, a node consists of the following data:

1. a min, a max, and a size element;
2. a pointer to a high-vEB; and
3. an array (called low[]) of size $\sqrt{u}$, each element of which stores a pointer to a vEB tree storing the keys in the range it is responsible for.

The idea now would be to replace the low-array by a hash table of, say, load factor $\alpha$. (Surely, someone has thought of that before.)

Now, let's assume that $n << u$, in particular $n = u^{\frac{1}{2^k}}$, and that the keys are uniformly distributed over the universe.

Then, the space complexity would be something like $S(n,u) = \frac{n}{\alpha} + S(1,\sqrt{u}) \cdot n + S(n,\sqrt{u})$, because we would have one key per child-vEB and n keys in the high-vEB.

That would give us $O( \log \log(u) \cdot n)$ space complexity, wouldn't it?

-