# Solving recurrence relation with square root

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 big $$O$$-notation for $$S(m)$$ 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 ?

• Possible duplicate of Solving or approximating recurrence relations for sequences of numbers Aug 14, 2017 at 19:26
• The recurrence relation would not be $O(\log \log n)$ unless it were constant work per recurrence. e.g. $T(n) = T(\sqrt{n}) + 1$.
– ryan
Aug 14, 2017 at 20:10
• S(m) = S(m/2) + 2^m, not S(m/2) + m. Jun 23, 2019 at 19:36

The answer cannot be $$O(\log\log n)$$. Already without applying any recursion we have the inequality $$T(n) = T(\sqrt{n}) + n \ge n$$. So the complexity cannot be smaller than $$O(n)$$.

But now to your computation. Setting $$n=2^m$$, we obtain as you did $$T(2^m) = T(\sqrt{2 ^ m}) + 2^m=T(2 ^ {\frac{m}{2}}) + 2^m.\tag{1}\label{eq1}$$ You defined $$S(m) = T(2^m).$$ Then equation $$\eqref{eq1}$$ should become the following equation, which is different from $$S(m)\,= S(\frac{m}{2})\, + m$$, the wrong equation in the question.

$$S(m) = S\left(\frac{m}{2}\right) + 2^m.$$

The equation above 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)$$.

• When transforming T to S we write 2^m as m, then why don't we write m instead of 2^m at the end ? Aug 15, 2017 at 4:23
• @Zephyr You need to be quite careful here. We defined the new function $S(m) := T(2^m)$. This means that we can replace $T(2^m)$ by $S(m)$, and $T(2^{m/2})$ by $S(m/2)$. But this doesn't mean that $2^m$ gets replaced by $m$. Aug 15, 2017 at 6:11
• Replacing all $2^m$ terms by $m$ wouldn't make any sense. You would take the $\log$ of some function arguments, and of the constant term at the end. That's not allowed. $\log(x+y) \ne \log(x) + \log(y)$. Aug 15, 2017 at 6:19
• Thanks for the answer. Can you help me with this question cs.stackexchange.com/q/80082/63873? Aug 15, 2017 at 6:51

The transformation:

You define $$S(m) = T(2^m)$$ which is absolutely fine.

$$T(m) = T(m^{1/2}) + m$$, so $$T(2^m) = T(2^{m/2}) + 2^m$$.

Therefore $$S(m) = T(2^m) = T(2^{m/2}) + 2^m = S(m/2) + 2^m$$. That's the mistake you made, the last term is $$2^m$$ and not $$m$$.

Try $$n = 2^{1024}$$: $$T(2^{1024}) = T(2^{512}) + 2^{1024} = T(2^{256}) + 2^{512} + 2^{1024}$$ and so on. All the bits you add up are negligible compared to the $$2^{1024}$$.

• Thanks for the answer but I asked that question 2 years ago. Now I am familiar with solving recurrences. Jun 24, 2019 at 19:41
• @Zephyr It looks like you misunderstood the fundamental purpose of this site. This site is not only about helping the individual who raised a particular question, but also about a knowledge database in the form of easily-searchable users-voted question and answers. Each question and answer is supposed to last forever. Or as long as possible. Jun 25, 2019 at 18:47
• @Zephyr In other words, gnasher729's answering does not imply you do not know the answer now. In fact, many questions have been raised by people who then provide excellent answers to those questions. Jun 25, 2019 at 21:50

Complexity of above recurrence is O(m) which is O(log m) and now n = 2 ^m so m = log n and hence complexity is O(log log n).

• We're looking for answers that explain what's going on, not just claims that some particular function is a solution. Jun 24, 2019 at 15:32
• Also, the accepted answer shows why the answer can't be this. Jun 25, 2019 at 16:55