Suppose we are given a sorted array A$[1...$ n$],$ and we wish to determine where in A the element x belongs$$that is$,$ the index i such that A$[$i $1]$ x A$[$i$].($Binary Search solves this problem.$)$ Here$$s a sketch of an algorithm rootSearch to solve this problem:

$$ if n is small $($say$,$ less than $100),$ find the index by brute force. Otherwise:

$$ define mileposts :$=$ A$[$n$],$ A$[2$n$],$ A$[3$n$],...,$ A$[$n$]$ to be a list of every $($n$)$th element of A$.$

$$ recursively, find post :$=$ rootSearch$($mileposts$,$ x$).$

$$ return rootSearch$($A$[($post $1)$n$,...,$ post$$n$],$ x$).$

$($Note that rootSearch makes two recursive calls.$)$ Find a recurrence relation for the running time of this

algorithm, and solve it$.$A van Emde Boas tree is a recursive data structure $($with somewhat similar inspiration to Q$3$ above$)$

that allows us to insert,

delete, and look up keys drawn from a set $U=1,2,$dots,$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(u)=T(\sqrt[\phantom{2}]{?}u)+1$ and $T(1)=1$

Solve this recurrence.

$($Hint: it is much easier using a change of variable method e$.$g$.$ define $S(k)=T(2^k).$ Solving $S(k)$

is easier!$)$