in Algorithms
1,378 views
0 votes
0 votes
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...
in Algorithms
1.4k views

1 Answer

6 votes
6 votes
Best answer
$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)$
selected by

1 comment

nice.
1
1