1,378 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...

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

here a = 2, b = 4 and k = $\frac{1}{2}$

$b^k = 4^{\frac{1}{2}}$ = 2

$a = b^k$ (Case 2 of Master’s theorem)

Now  p = 0 (Case 2(a) of Master’s theorem)

Therefore $T(n) = O(n^{\frac{1}{2}} logn)$
by

nice.

1
148 views