4-1 Recurrence examples

Give asymptotic upper and lower bound for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for $n \le 2$. Make your bounds as tight as possible, and justify your answers.

a. $T(n) = 2T(n / 2) + n^4$.

b. $T(n) = T(7n / 10) + n$.

c. $T(n) = 16T(n / 4) + n^2$.

d. $T(n) = 7T(n / 3) + n^2$.

e. $T(n) = 7T(n / 2) + n^2$.

f. $T(n) = 2T(n / 4) + \sqrt n$.

g. $T(n) = T(n - 2) + n^2$.

a. By master theorem, $T(n) = \Theta(n^4)$.

b. By master theorem, $T(n) = \Theta(n)$.

c. By master theorem, $T(n) = \Theta(n^2\lg n)$.

d. By master theorem, $T(n) = \Theta(n^2)$.

e. By master theorem, $T(n) = \Theta(n^{\lg 7})$.

f. By master theorem, $T(n) = \Theta(\sqrt n \lg n)$.

g. Let $d = m \mod 2$,

$$ \begin{aligned} T(n) & = \sum_{j = 1}^{j = n / 2} (2j + d)^2 \\ & = \sum_{j = 1}^{n / 2} 4j^2 + 4jd + d^2 \\ & = \frac{n(n + 2)(n + 1)}{6} + \frac{n(n + 2)d}{2} + \frac{d^2n}{2} \\ & = \Theta(n^3). \end{aligned} $$