4-3 More recurrence examples
Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for sufficiently small $n$. Make your bounds as tight as possible, and justify your answers.
a. $T(n) = 4T(n / 3) + n\lg n$.
b. $T(n) = 3T(n / 3) + n / \lg n$.
c. $T(n) = 4T(n / 2) + n^2\sqrt n$.
d. $T(n) = 3T(n / 3 - 2) + n / 2$.
e. $T(n) = 2T(n / 2) + n / \lg n$.
f. $T(n) = T(n / 2) + T(n / 4) + T(n / 8) + n$.
g. $T(n) = T(n - 1) + 1 / n$.
h. $T(n) = T(n - 1) + \lg n$.
i. $T(n) = T(n - 2) + 1 / \lg n$.
j. $T(n) = \sqrt nT(\sqrt n) + n$
[This problem is solved only for parts a, c, e, f, g, h, and i.]
a. $T(n) = 3T(n / 2) + n\lg n$
We have $f(n) = n\lg n$ and $n^{\log_b a} = n^{\lg 3} \approx n^{1.585}$. Since $n\lg n = O(n^{\lg 3 - \epsilon})$ for any $0 < \epsilon \le 0.58$, by case 1 of the master theorem, we have $T(n) = \Theta(n^{\lg 3})$.
b. $\Theta(n\lg\lg n)$. Check subtask 5 for the reasoning.
c. $T(n) = 4T(n / 2) + n^2 \sqrt n$
We have $f(n) = n^2 \sqrt n = n^{5 / 2}$ and $n^{\log_b a} = n^{\lg 4} = n^2$. Since $n^{5 / 2} = \Omega(n^{2 + \epsilon})$ for $\epsilon = 1 / 2$, we look at the regularity condition in case 3 of the master theorem. We have
$$af(n / b) = 4(n / 2)^2 \sqrt{n / 2} = n^{5 / 2} / \sqrt 2 \le cn^{5 / 2}$$
for $1 / \sqrt 2 \le c < 1$. Case 3 applies, and we have $T(n) = \Theta(n^2 \sqrt n)$.
d. $\Theta(n\lg n)$ by the master method.
e. $T(n) = 2T(n / 2) + n / \lg n$
We can get a guess by means of a recursion tree:
We get the sum on each level by observing that at depth $i$, we have $2^i$ nodes, each with a numerator of $n / 2^i$ and a denominator of $\lg(n / 2^i) = \lg n - i$, so that the cost at depth $i$ is
$$2^i \cdot \frac{n / 2^i}{\lg n - i} = \frac{n}{\lg n - i}.$$
The sum for all levels is
$$ \begin{aligned} \sum_{i = 0}^{\lg n - 1} \frac{n}{\lg n - i} & = n \sum_{i = 1}^{\lg n} \frac{n}{i} \\ & = n \sum_{i = 1}^{\lg n} 1 / i \\ & = n \cdot \Theta(\lg\lg n) & \text{(by equation (A.7), the harmonic series)} \\ & = \Theta(n\lg\lg n). \end{aligned} $$
We can use this analysis as a guess that $T(n) = \Theta(n\lg\lg n)$. If we were to do a straight substitution proof, it would be rather involved. Instead, we will show by substitution that $T(n) \le n(1 + H_{\lfloor \lg n \rfloor})$ and $T(n) \ge n \cdot H_{\lceil \lg n \rceil}$, where $H_k$ is the $k$th harmonic number: $H_k = 1 / 1 + 1 / 2 + 1 / 3 + \cdots + 1 / k$. We also define $H_0 = 0$. Since $H_k = \Theta(\lg k)$, we have that $H_{\lfloor \lg n \rfloor} = \Theta(\lg \lfloor \lg n \rfloor) = \Theta(\lg\lg n)$ and $H_{\lceil \lg n \rceil} = \Theta(\lg \lceil \lg n \rceil) = \Theta(\lg\lg n)$. Thus, we will have that $T(n) = \Theta(n\lg\lg n)$.
The base case for the proof is for $n = 1$, and we use $T(1) = 1$. Here, $\lg n = 0$, so that $\lg n = \lfloor \lg n \rfloor = \lceil \lg n \rceil$. Since $H_0 = 0$, we have $T(1) = 1 \le 1(1 + H_0)$ and $T(1) = 1 \ge 0 = 1 \cdot H_0$.
For the upper bound of $T(n) \le n(1 + H_{\lfloor \lg n \rfloor})$, we have
$$ \begin{aligned} T(n) & = 2T(n / 2) + n / \lg n \\ & \le 2((n / 2)(1 + H_{\lfloor \lg (n / 2) \rfloor})) + n / \lg n \\ & = n(1 + H_{\lfloor \lg n - 1 \rfloor}) + n / \lg n \\ & = n(1 + H_{\lfloor \lg n \rfloor - 1} + 1 / \lg n) \\ & \le n(1 + H_{\lfloor \lg n \rfloor - 1} + 1 / \lfloor \lg n \rfloor) \\ & = n(1 + H_{\lfloor \lg n \rfloor}), \end{aligned} $$
where the last line follows from the identity $H_k = H_{k - 1} + 1 / k$.
The upper bound of $T(n) \ge n \cdot H_{\lceil \lg n \rceil}$ is similar:
$$ \begin{aligned} T(n) & = 2T(n / 2) + n / \lg n \\ & \ge 2((n / 2) \cdot H_{\lceil \lg (n / 2) \rceil}) + n / \lg n \\ & = n \cdot (H_{\lceil \lg n - 1 \rceil}) + n / \lg n \\ & = n \cdot (H_{\lceil \lg n \rceil - 1} + 1 / \lg n) \\ & \ge n \cdot (H_{\lceil \lg n \rceil - 1} + 1 / \lceil \lg n \rceil) \\ & = n \cdot (H_{\lceil \lg n \rceil}). \end{aligned} $$
Thus, $T(n) = \Theta(n\lg\lg n)$.
f. $T(n) = T(n / 2) + T(n / 4) + T(n / 8) + n$
Using the recursion tree shown below, we get a guess of $T(n) = \Theta(n)$.
We use the substitution method to prove that $T(n) = O(n)$. Our inductive hypothesis is that $T(n) \le cn$ for some constant $c > 0$. We have
$$ \begin{aligned} T(n) & = T(n / 2) + T(n / 4) + T(n / 8) + n \\ & \le cn / 2 + cn / 4 + cn / 8 + n \\ & = 7 cn / 8 + n \\ & = (1 + 7c / 8) n \\ & \le cn \quad \text{if $c \ge 8$}. \end{aligned} $$
Therefore, $T(n) = O(n)$.
Showing that $T(n) = \Omega(n)$ is easy:
$$T(n) = T(n / 2) + T(n / 4) + T(n / 8) + n \ge n.$$
Since $T(n) = O(n)$ and $T(n) = \Omega(n)$, we have that $T(n) = \Theta(n)$.
g. $T(n) = T(n - 1) + 1 / n$
This recurrence corresponds to the harmonic series, so that $T(n) = H_n$, where $H_n = 1 / 1 + 1 / 2 + 1 / 3 + \cdots + 1 / n$. For the base case, we have $T(1) = 1 = H_1$. For the inductive step, we assume that $T(n - 1) = H_{n - 1}$, and we have
$$ \begin{aligned} T(n) & = T(n - 1) + 1 / n \\ & = H_{n - 1} + 1 / n \\ & = H_n. \end{aligned} $$
Since $H_n = \Theta(\lg n)$ by equation $\text{(A.7)}$, we have that $T(n) = \Theta(\lg n)$.
h. $T(n) = T(n - 1) + \lg n$
We guess that $T(n) = \Theta(n\lg n)$. To prove the upper bound, we will show that $T(n) = O(n\lg n)$. Our inductive hypothesis is that $T(n) \le cn\lg n$ for some constant $c$. We have
$$ \begin{aligned} T(n) & = T(n - 1) + \lg n \\ & \le c(n - 1) \lg(n - 1) + \lg n \\ & = cn\lg(n - 1) - c \lg(n - 1) + \lg n \\ & \le cn\lg(n - 1) - c \lg(n / 2) + \lg n & \text{(since $\lg(n - 1) \ge \lg(n / 2)$ for $n \ge 2$)} \\ & = cn\lg(n - 1) - c \lg n + c + \lg n \\ & < cn\lg n - c \lg n + c + \lg n \\ & \le cn\lg n, \end{aligned} $$
if $-c \lg n + c + \lg n \le 0$. Equivalently,
$$ \begin{aligned} -c \lg n + c + \lg n & \le 0 \\ c & \le (c - 1) \lg n \\ \lg n & \ge c / (c - 1). \end{aligned} $$
This works for $c = 2$ and all $n \ge 4$.
To prove the lower bound, we will show that $T(n) = \Omega(n\lg n)$. Our inductive hypothesis is that $T(n) \ge cn\lg n + dn$ for constants $c$ and $d$. We have
$$ \begin{aligned} T(n) & = T(n - 1) + \lg n \\ & \ge c(n - 1) \lg(n - 1) + d(n - 1) + \lg n \\ & = cn\lg(n - 1) - c \lg(n - 1) + dn - d + \lg n \\ & \ge cn\lg(n / 2) - c \lg(n - 1) + dn - d + \lg n & \text{(since $\lg(n - 1) \ge \lg(n / 2)$ for $n \ge 2$)} \\ & = cn\lg n - cn - c \lg(n - 1) + dn - d + \lg n \\ & \ge cn\lg n, \end{aligned} $$
if $-cn - c \lg(n - 1) + dn - d + \lg n \ge 0$. Since
$$-cn - c \lg(n - 1) + dn - d + \lg n > -cn - c\lg(n - 1) + dn - d + \lg(n - 1),$$
it suffices to find conditions in which $-cn - c\lg(n - 1) + dn - d + \lg(n - 1) \ge 0$. Equivalently,
$$ \begin{aligned} -cn - c \lg(n - 1) + dn - d + \lg(n - 1) & \ge 0 \\ (d - c)n & \ge (c - 1)\lg(n - 1) + d. \end{aligned} $$
This works for $c = 1$, $d = 2$, and all $n \ge 2$.
Since $T(n) = O(n\lg n)$ and $T(n) = \Omega(n\lg n)$, we conclude that $T(n) = \Theta(n\lg n)$.
i. $T(n) = T(n - 2) + 2\lg n$
We guess that $T(n) = \Theta(n\lg n)$. We show the upper bound of $T(n) = O(n\lg n)$ by means of the inductive hypothesis $T(n) \le cn\lg n$ for some constant $c > 0$. We have
$$ \begin{aligned} T(n) & = T(n - 2) + 2\lg n \\ & \le c(n - 2)\lg(n - 2) + 2\lg n \\ & \le c(n - 2)\lg n + 2\lg n \\ & = (cn - 2c + 2)\lg n \\ & = cn\lg n + (2 - 2c)\lg n \\ & \le cn\lg n & \text{if $c > 1$}. \end{aligned} $$
Therefore, $T(n) = O(n\lg n)$.
For the lower bound of $T(n) = \Omega(n\lg n)$, we'll show that $T(n) \ge cn\lg n + dn$, for constants $c, d > 0$ to be chosen. We assume that $n \ge 4$, which implies that
- $\lg(n - 2) \ge \lg(n / 2)$,
- $n / 2 \ge \lg n$, and
- $n / 2 \ge 2$.
(We'll use these inequalities as we go along.) We have
$$ \begin{aligned} T(n) & \ge c(n - 2)\lg(n - 2) + d(n - 2) + 2\lg n \\ & = cn\lg(n - 2) - 2c\lg(n - 2) + dn - 2d + 2\lg n \\ & > cn\lg(n - 2) - 2c\lg n + dn - 2d + 2\lg n & \text{(since $-\lg n < -\lg(n - 2)$)} \\ & = cn\lg(n - 2) - 2(c - 1)\lg n + dn - 2d & \text{(by inequality (1) above)} \\ & = cn\lg n - cn - 2(c - 1)\lg n + dn - 2d \\ & \ge cn\lg n, \end{aligned} $$
if $-cn - 2(c - 1)\lg n + dn - 2d \ge 0$ or, equivalently, $dn \ge cn + 2(c - 1)\lg n + 2d$. Pick any constant $c > 1 / 2$, and then pick any constant $d$ such that
$$d \ge 2(2c - 1).$$
(The requirement that $c > 1 / 2$ means that $d$ is positive.) Then
$$d / 2 \ge 2c - 1 = c + (c - 1),$$
and adding $d / 2$ to both sides, we have
$$d \ge c + (c - 1) + d / 2.$$
Multiplying by $n$ yields
$$dn \ge cn + (c - 1)n + dn / 2,$$
and then both multiplying and dividing the middle term by $2$ gives
$$dn \ge cn + 2(c - 1)n / 2 + dn / 2.$$
Using inequalities (2) and (3) above, we get
$$dn \ge cn + 2(c - 1)\lg n + 2d,$$
which is what we needed to show. Thus $T(n) = \Omega(n\lg n)$. Since $T(n) = O(n\lg n)$ and $T(n) = \Omega(n\lg n)$, we conclude that $T(n) = \Theta(n\lg n)$.
j. $T(n) = \sqrt nT(\sqrt n) + n$
We guess $T(n) \le cn\lg\lg n$,
$$ \begin{aligned} T(n) & \le \sqrt nc\sqrt n\lg\lg\sqrt n + n \\ & = cn\lg\lg\sqrt n + n \\ & = cn\lg\frac{\lg n}{2} + n \\ & = cn\lg\lg n - cn\lg 2 + n \\ & = cn\lg\lg n + (1 - c)n & (c > 1) \\ & \le cn\lg\lg n. & = \Theta(n\lg\lg n) \end{aligned} $$