38 views

Use the master method to give tight asymptotic bounds for the following recurrences.

1. $T(n)=2T(n/4) + 1$
2. $T(n)=2T(n/4) +\sqrt{n}$
3. $T(n)=2T(n/4) +n$
4. $T(n)=2T(n/4) +n^2$

edited | 38 views
0
1. $\Theta$(√ n)

2.$\Theta (√ n)logn$

3.$\Theta (n)$

4.$\Theta (n^2)$