Masters theorem

Question

Comments

c) O(n) ??

---

Master method can't be applied here. Right??

---

@Rishab

we can substitute $n=2{^m}$ and can proceed further

---

@Ashwani Oh! Yes

Answer 1

Given $T(n)=2T(\sqrt n) + n$

Substitute $n=2{^m}$, we get

$T(2^{m})=2T(2^{m/2}) +2^{m}$

We can write a new recurrence relation as

$S(m)=2S(m/2) +2^{m}$

$S(m)=\Theta (2^{m})$

$T(n)=\Theta (n)$

Hence option c) is correct

Comments

how did you proceed from line 5 to 6 in your answer?

Answer 2

put n=2^m

T(2^m)=T(2^(m/2))+2^m

T(2^m)=S(m)

S(m)=S(m/2)+2^m

use master theorem

m^(log2)=m

2^m=w(m)

so ,

S(m)=2^m

T(2^m)=2^m

T(n)=n

Answer 3

O(n)

Comments

did you consider 2^m as constant, if yes then why?

Please explain

Answer 4

substitute n = 2^m

Then apply master's theorem.

you'll get O(n).

Comments

@Ashwin Kulkarni , after substituting we get f(m) = 2*f(m/2)+2^m, so do we have to take 2^m as constant?

---

We are not considering 2^m as constant...

Actually when T(2^m)=s(m)

So , T(2^m/2) + 2^m  becomes

S(m)=S(m/2) + m ......

---

I think answer is not O(n).After reading similar type of question and answer we are assuming that answer will be this.I this is case of change variable.we have to solve properly taking substitution rather guessing answer.Otherwise confusion will not be clear.If possible please solve.

Before applying Master theorem we should be careful whether it is applicable to particular problem or not.