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}
\]
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用