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}$$