Solve the following recurrence relations using masters method. a. T(n) = 2T(n/4) + kn2, n > 1; T(1) = 1 b. T(n) = 5T(n/4) + kn, n > 1; T(1) = 1

For $T(n) = aT(n/b) + f(n)$ with $a \geq 1$, $b 1$, compare $f(n)$ with $n^{\logb a}$: - Case 1: $f(n) = O(n^{\logb a - \epsilon})$ $\Rightarrow$ $T(n) = \Theta(n^{\logb a})$ - Case 2: $f(n) = \Theta(n^{\logb a})$ $\Rightarrow$ $T(n) = \Theta(n^{\logb a}\log n)$ - Case 3: