What is the recurrence for T(n)=2T(n/4)+sqrt(n) using the Master Theorem

Question

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...

Answer 1

$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)$

Comments

nice.