Return to Question

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

It's easy to get the recurrence S(u²) = (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

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.