3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – Scott Morrison
    Oct 24, 2009 at 7:05
  • $\begingroup$ Great advice, thank you! (here tough I'm happy I got a quick and excellent answer, but for the next time) $\endgroup$
    – didest
    Oct 24, 2009 at 7:36
  • 1
    $\begingroup$ 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 $\endgroup$
    – David Eppstein
    Oct 17, 2010 at 6:25

3 Answers 3

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm quite embarrased to know it was so easy. Thanks! $\endgroup$
    – didest
    Oct 24, 2009 at 6:58
  • $\begingroup$ 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. $\endgroup$
    – aorq
    Oct 24, 2009 at 7:04
  • $\begingroup$ 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$? $\endgroup$
    – Gab
    May 24, 2011 at 13:13
  • $\begingroup$ 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? $\endgroup$
    – Emil Jeřábek
    May 24, 2011 at 13:33
0
$\begingroup$

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

Improve this answer
$\endgroup$
-1
$\begingroup$

Please refer the attached image, Here I directly applied the substitution method from CLRS book.

Substitution method CLRS

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It is better to use Math Jax to write mathematical text for otherwise the content is not searchable thus someone interested in your research cannot find what is looking for. $\endgroup$
    – Daniele Tampieri
    Feb 13 at 7:51
  • $\begingroup$ Instead of linking to an image, please include the text in your post. $\endgroup$
    – Stefan Kohl ♦
    Feb 13 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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