Solving Recrrence

Question

Consider the following recurrence T(n) = 3T(n/5) + lgn * lgn What is the value of T(n)? 
(A) 
(B) 
(c) 
(D) 

Comments

http://stackoverflow.com/questions/7280224/solving-the-recurrence-relation-tn-√n-t√n-n

Proof of height.

---

The next term is always root of the previous term.

So, terms will be like n + n^1/2 + n^1/4 + n^1/8 .........+ 1

So, n ^ (1/ 2ⁱ) = 2

Now, if you take RHS=1, then taking log of both sides will give (1/ 2ⁱ)logn = 0. So, we wont able to proceed further. Hence, I took RHS=2.

Taking log of both sides, (1/ 2ⁱ)logn = 1

thus, 2ⁱ = logn

Thus, i = height = loglogn

---

@shushant thanks

Answer 1

n^log ₅3  = n ^0.68 and f(n) = logn*logn

Had been f(n) = n^0.67 then we would have T(n) = $\Theta$(n^0.68)

Now, we compare logn*logn with n^0.67 to know if we can approximate by 

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

we take log of both sides:  log(logn * logn) < 0.67 * logn

So, we can approximate f(n) by n^0.67 and conclude that T(n) = $\Theta$(n^0.68)