Design and Analysis of Algorithms20815 marksNumerical: Master's theorem recurrenceSolving Recurrences
Solve the following recurrence relations using master's method. 1. T(n) = 2Tleft(fracn2right) + n3, n > 1;quad T(n) = 1, n = 1 2. T(n) = 2Tleft(fracn4right) + 1, n > 1;quad T(n) = 1, n = 1
Solve the following recurrence relations using master's method.
-
$T(n) = 2T\left(\frac{n}{2}\right) + n^3,\ n > 1;\quad T(n) = 1,\ n = 1$
-
$T(n) = 2T\left(\frac{n}{4}\right) + 1,\ n > 1;\quad T(n) = 1,\ n = 1$
[5]
For $T(n) = aT\left(\frac{n}{b}\right) + f(n)$ with $a \geq 1$, $b 1$: Compute the critical exponent $\logb a$ and compare $f(n)$ with $n^{\logb a}$: Case Condition Result ------------------------- 1 $f(n) = O(n^{\logb a - \epsilon})$, $\epsilon 0$ $T(n) = \Theta(n^{\logb a})$ 2