Solve Recurrence Equation T(n) = 2T(n/4) + √3

262 Views Asked by At

I've been struggling to come to exact solution for this. I'm using Recursion tree to solve this. Which is giving me θ(n) as an answer.

Steps : =>

            1) T(n) = 2T(n/4) + √3

            2) Emerging Pattern => (1/2^k) * n 

            3) Considering , when we break down to T(1) : :   (1/2^k) * n  = 1

            4) k = log (n)

            5) Each level has 2^i nodes :: 2^(log (n)) :=> n

            6) If you sum up cost , n + n/2 + n/4 + ..... = n*(1/1-(1/2))

Which is incorrect ,

Answer given is ( √n log n ) , would appreciate any help regarding same ?