Recurrence Relation

Question

$T(n) = 2T(\sqrt{n}) + n$

Comments

you can refer this link :-https://www.quora.com/What-is-the-complexity-of-recurrence-relation-T-n-2T-root-n-+n

---

Thanks, @Akshay Koli 4 I solved it using the same as mentioned in Quora, but I want to know the steps, using substitution method as this method doesn't apply to every question.

---

@Shubhanshu  do you also used master theorem ??   vivek verma applied master theorem  , but i dont think it can be applied

---

What he did is correct.

---

@Shubhanshu  can you expllain it why , it will be helpful iam stuck in question , thanks in advance

---

Step 1) Take $n = 2^k$

You will get modified equation as $T(2^k) = 2T(2^{k/2}) + 2^k$.....(iii)

Step 2) $T(2^k) = S(k)$ ...... (i)

and put k = k/2.

You will get $T(2^{k/2}) = S(k/2)$ .....(ii)

Now from (i) and (ii) modified equation is:-

$S(k) = 2S(k/2) + 2^k$

Use Master's theorem now, it will be easy.

---

https://gateoverflow.in/197417/please-solve-this-q

---

@hacker16 I know it is easy to solve it by the method in your answer, but do you know how to solve this question without that way?

---

answer is wrong there , answer is $\Theta (n)$ @hacker16 

---

T(n) = aT$(\frac{n}{b}) + \Theta (n^k log^{p} n)$

so in equation we have  $2^k$  or let say $2^n$

its not $n^2$  

so  we cannot apply masters ?? correct me if iam wrong

Shubhanshu  

---

may be this might help https://gateoverflow.in/841/gate2002-2-11

---

@sumit goyal 1 f(k) which is 2^k (exponential function) is bigger than 2S(k/2). Hence, it will be the TC. or TC = O(2^k) or O(n) as 2^k = n.

---

T(n) = $8T(\frac{n}{2})+ n^2$

answer = $\Theta (n^3)$

if i apply that logic here  that  n$^2$  >>  T$(\frac{n}{2})$  = O($(n^2)$

it failed here not a good approach  @Shubhanshu according to me bro 

---

did u get the explanation here ?

Answer 1

it should be o(n)