# 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} $$