I am trying to solve the following recurrence relation :-$T(n) = T(\sqrt{n}) + n$ using masters theorem.We can substitute $n = 2 ^ m$$T(2^m) = T(2 ^ {\frac{m}{2}}) + 2^m$Now we can rewrite it as$S(m) = S(\frac{m}{2}) + m$The complexity of the above recurrence will be $O(m)$Hence, $T(n) = T(2^m) = S(m) = O(m)$.So we can say that $T(n) =O(\log n)$ as $n=2^m$.But the answer is $O(\log\log n)$ . What is wrong with my approach ?
Solving recurrence relation with square root
algorithms;time complexity;recurrence relation;master theorem
The answer cannot be $O(\log\log n)$. Already without applying any recursion we have the inequality $T(n) = T(\sqrt{n}) + n >= n$. So the complexity cannot be smaller than $O(n)$. But now to your computation. You made a mistake when you transformed from $T$ to $S$. You defined $S(m) = T(2^m)$. But this gives the following equation:$$S(m) = S\left(\frac{m}{2}\right) + 2^m$$This falls into the third case of the master theorem, therefore $S(m) \in \Theta(2^m)$. And from this follows $T(n) \in \Theta(n)$.