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.

*

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


*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.
 A: 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.
A: 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
