# More recurrence induction examples

### Question

Assume $$n = 2^{2^k}$$ for some integer k.

Consider the following recurrence:

$$\begin{split} T(n) = \left\{ \begin{array}l 1, &if\ n = 2 \\ \sqrt{n}T(\sqrt{n}) + n, &if\ n > 2 \end{array} \right. \end{split}$$

On unfolding this recurrence, we get

$$\begin{split} T(n) &= \sqrt{n} ( n^{1/4} T(n^{1/4}) ) + n &= n^{3/4}T(n^{1/4}) + 2n \\ &= n^{3/4}(n^{1/8}T(n^{1/8}) + n^{1/4}) + 2n &= n^{7/8}T(n^{1/8}) + 3n \end{split}$$

Guess:

$$T(n) = n^{1 - 1/2^{i}}T(n^{1/2^i}) + i · n \ for \ 1 \leq i \leq k , n > 2 \ \ \ - \ (1)$$

### Proof by induction

For i = 1:

$$\begin{split} T(n) &= n^{1 - 1/2}T(n^{1/2}) + n \\ &= n^{1/2}T(n^{1/2}) + n \end{split}$$

For i = j:

$$T(n) = n^{1 - 1/2^{j}}T(n^{1/2^j}) + j · n$$

Show for i = j + 1:

$$T(n) = n^{1 - 1/2^{j + 1}}T(n^{1/2^{j + 1}}) + (j + 1) · n$$

Prove for i = j + 1:

$$\begin{split} T(n) &= n^{1 - 1/2^{j}}T(n^{1/2^j}) + j · n \\ &= n^{1 - 1/2^{j}} · (n^{1/2^{j + 1}} T(n^{1/2^{j + 1}}) + n^{1/2^j}) + j · n \\ &= n^{1 - 1/2^{j + 1}}T(n^{1/2^{j + 1}}) + n + j · n \\ &= n^{1 - 1/2^{j + 1}}T(n^{1/2^{j + 1}}) + (j + 1) · n \end{split}$$

Solve for:

$$\begin{split} n &= 2^{2^k} \\ loglogn &= k \end{split}$$

Substitute into (1):

$$\begin{split} T(n) &= n^{1 - 1/2^{loglogn}}T(n^{1/2^{loglogn}}) + loglogn · n \\ &= n^{1 - 1/logn}T(n^{1/logn}) + n\ log \log n \\ &= \Theta(n\log \log n) \end{split}$$