Problem 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.

  1. $T(n) = 2T(n/2) + n^4$
  2. $T(n) = T(7n/10) + n$
  3. $T(n) = 16T(n/4) + n^2$
  4. $T(n) = 7T(n/3) + n^2$
  5. $T(n) = 7T(n/2) + n^2$
  6. $T(n) = 2T(n/4) + \sqrt{n}$
  7. $T(n) = T(n - 2) + n^2$
  1. $\Theta(n^4)$ (master method)
  2. $\Theta(n)$ (master method, $\log_{10/7}1 = 0$)
  3. $\Theta(n^2\lg{n})$ (master method)
  4. $\Theta(n^2)$ (master method)
  5. $\Theta(n^{\log_2{7}})$ (master method)
  6. $\Theta(\sqrt{n}\lg_{n})$ (master method)
  7. $T(n) = n^2 + T(n - 2) = n^2 + (n - 2)^2 + T(n - 4) = \sum_{i=0}^{n/2}(n -2i)^2 = \Theta(n^3)$