0
$\begingroup$

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 ?

$\endgroup$
5
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Zephyr Aug 15 '17 at 4:23
  • $\begingroup$ @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$. $\endgroup$ – Jakube Aug 15 '17 at 6:11
  • $\begingroup$ 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)$. $\endgroup$ – Jakube Aug 15 '17 at 6:19
  • $\begingroup$ Thanks for the answer. Can you help me with this question cs.stackexchange.com/q/80082/63873? $\endgroup$ – Zephyr Aug 15 '17 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.