# 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 ?

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 ? – Zephyr Aug 15 '17 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$. – Jakube Aug 15 '17 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)$. – Jakube Aug 15 '17 at 6:19
• Thanks for the answer. Can you help me with this question cs.stackexchange.com/q/80082/63873? – Zephyr Aug 15 '17 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. – Zephyr Jun 24 '19 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. – John L. Jun 25 '19 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. – John L. Jun 25 '19 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. – David Richerby Jun 24 '19 at 15:32
• Also, the accepted answer shows why the answer can't be this. – Raphael Jun 25 '19 at 16:55