A van Emde Boas tree is a recursive data structure (with somewhat similar inspiration to the previous exercise) that allows us to insert, delete, and look up keys drawn from a set U = {1, 2, . . . ,...

A van Emde Boas tree is a recursive data structure (with somewhat similar inspiration to the previous exercise) that allows us to insert, delete, and look up keys drawn from a set U = {1, 2, . . . , u} quickly. (It solves the same problem that binary search trees solve, but our running time will be in terms of the size of the universe U rather than in terms of the number of keys stored.) A van Emde Boas tree achieves a running time given by T(n) = T( √ n) + 1 and T(1) = 1. Solve this recurrence. (Hint: define R(k) := T(2k ). Solving R(k) is easy!)