SOLVING RECURRENCE RELATION BY BACK SUBSTITUTION

Question

solution of t(n)= t(sqrt(n)) + n using back substitution

Answer 1

Answer
Correct me if I am wrong

Comments

Actually I have got it from the base condition of the recurrence.
It is not mentioned in the question.
You have to consider that
T(n)=1       n=2

T(n) = (n^1/2)+n     n>2

---

Got it. Thanks bro.

---

its welcome , bro

Answer 2

put t=2pow(k)

T(2k)=T((2k)1/2)+n

 

again put T(2k)=P(k)

and solve...