Recursion

Question

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

How to solve this?

Comments

Method #1 : solve recursively

T(n) =logn + T(√n)

T(n)=logn+logn^1/2+logn^1/4+logn^1/8+....

T(n)=log(n*n^1/2*n^1/4*n^1/8*.....)

T(n)=log(n*n)=logn²=O(logn)

---

Method #2 reshape into master theorem

let n=2^m      // logn=m

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

Let T(2^m)=S(m)

S(m)=S(m/2)+m    // by master theorem it's O(m)

and O(m) means O(logn)