4.3 The substitution method for solving recurrences

4.3-1

We start by assuming that this bound holds for all positive m < n, in particular for m = n - 1, yielding $T(n - 1) \leq c(n - 1)^2$. Substituting into the recurrence yields:

$$T(n) = T(n - 1) + n \leq c(n - 1)^2 + n = cn^2 + (1 - 2c)n + c \leq cn^2$$

where the last step holds as long as $c > \frac{1}{2}$ and $n \geq \frac{c}{2c - 1}$.

4.3-2

We start by assuming that $T(n) \leq c\lg{n}$ holds for all positive m < n, in particular for $m = \lceil \frac{n}{2} \rceil$, yielding $T(\lceil \frac{n}{2} \rceil) \leq c\lg{\lceil \frac{n}{2} \rceil}$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} T(n) &=& T(\lceil \frac{n}{2} \rceil) + 1 \\ &\leq& c\lg{\lceil \frac{n}{2} \rceil} + 1 \leq c(\lg{(\frac{n + (2 - 1)}{2})}) + 1 \text{ (inequation 3.6) } \\ &=& c\lg{(n + 1)} - c + 1 \end{eqnarray} $$

But it's not easy to prove that $c\lg{(n + 1)} - c + 1 \leq c\lg{n}$, so we reguess $T(n) = O(\lg{(n - 1)})$, since if $T(n) = O(\lg{(n - 1)})$, then it's obviously $O(\lg{n})$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} T(n) &\leq& c\lg{(\lceil \frac{n}{2} \rceil -1)} + 1 \\ &\leq& c\lg{(\frac{n + (2 - 1)}{2} -1)} + 1 \\ &=& c\lg{(n - 1)} - c + 1 \leq c\lg{(n - 1)} < c\lg{n} \end{eqnarray} $$

where the last step holds as long as $c \geq 1$.

4.3-3

We start by assuming that $T(n) \geq cn\lg{n}$ holds for all positive m < n, in particular for $m = \lfloor \frac{n}{2} \rfloor$, yielding $T(\lfloor \frac{n}{2} \rfloor) \geq c\lfloor \frac{n}{2} \rfloor\lg{\lfloor \frac{n}{2} \rfloor}$. Substituting ino the recurrence yields:

$$T(n) = 2T(\lfloor \frac{n}{2} \rfloor) + n \geq 2c\lfloor \frac{n}{2} \rfloor\lg{\lfloor \frac{n}{2} \rfloor} + n \geq cn\lg(\frac{n}{2}) + n = cn\lg{n} + (1 - c)n \geq cn\lg{n}$$

where the last step holds as long as $c \leq 1$.

Since $T(n) = O(n\lg{n})$ and $T(n) = \Omega(n\lg{n})$, so $T(n) = \Theta(n\lg{n})$.

4.3-4

We can choose $T(n) = O(n\lg{n} + 1)$, then $T(n) \leq cn\lg{n} + 1$. It holds for the base case, since $c1\lg{1} + 1 = 1 \geq T(1)$.

4.3-5

First, let's prove $T(n) = O(n\lg{n})$. We start by assuming that $T(n) \leq cn\lg{n}$ holds for all positive m < n, yielding $T(\lceil \frac{n}{2} \rceil) \leq c\lceil \frac{n}{2} \rceil\lg{\lceil \frac{n}{2} \rceil}$ and $T(\lfloor \frac{n}{2} \rfloor) \leq c\lfloor \frac{n}{2} \rfloor\lg{\lfloor \frac{n}{2} \rfloor}$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} T(n) &=& T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + \Theta(n) \\ &\leq& c\lceil \frac{n}{2} \rceil\lg{\lceil \frac{n}{2} \rceil} + c\lfloor \frac{n}{2} \rfloor\lg{\lfloor \frac{n}{2} \rfloor} + \Theta(n) \\ &\leq& c(\frac{n + (2 - 1)}{2})\lg{(\frac{n + (2 - 1)}{2})} + c(\frac{n}{2})\lg{(\frac{n}{2})} + \Theta(n) \\ &=& c\frac{n + 1}{2}\lg{(n + 1)} + c\frac{n}{2}\lg{n} - cn + \Theta(n) - \frac{c}{2} \end{eqnarray} $$

It's also not easy to prove that $T(n) \leq cn\lg{n}$, so we try to guess $T(n) = O((n - 1)\lg{(n - 1)})$, so:

$$ \begin{eqnarray} T(n) &=& T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + \Theta(n) \\ &\leq& c(\lceil \frac{n}{2} \rceil - 1)\lg{(\lceil \frac{n}{2} \rceil - 1)} + c(\lfloor \frac{n}{2} \rfloor - 1)\lg{(\lfloor \frac{n}{2} \rfloor - 1)} + \Theta(n) \\ &\leq& c(\frac{n + (2 - 1)}{2} - 1)\lg{(\frac{n + (2 - 1)}{2} - 1)} + c(\frac{n}{2} - 1)\lg{(\frac{n}{2} - 1)} + \Theta(n) \\ &=& c\frac{n - 1}{2}\lg{(n - 1)} + c\frac{n - 2}{2}\lg{(n - 2)} - cn + \Theta(n) - \frac{3c}{2} \\ &<& c\frac{n - 1}{2}\lg{(n - 1)} + c\frac{n - 1}{2}\lg{(n - 1)} - cn + \Theta(n) - \frac{3c}{2} \\ &=& c(n - 1)\lg{(n - 1)} - cn + \Theta(n) - \frac{3c}{2} \\ &\leq& c(n - 1)\lg{(n - 1)} - cn + c_1n - \frac{3c}{2} \\ &=& c(n - 1)\lg{(n - 1)} + (c_1 - c)n - \frac{3c}{2} \\ &<& c(n - 1)\lg{(n - 1)} \\ &<& cn\lg{n} \end{eqnarray} $$

where the last step holds as long as $c > c_1$ and $n \geq \frac{3c}{2(c - c_1)}$.

Then let's prove $T(n) = \Omega(n\lg{n})$. We start by assuming that $T(n) \geq c(n + 1)\lg{(n + 1)}$ holds for all positive m < n, yielding $T(\lceil \frac{n}{2} \rceil) \geq c(\lceil \frac{n}{2} \rceil + 1)\lg{(\lceil \frac{n}{2} \rceil + 1)}$ and $T(\lfloor \frac{n}{2} \rfloor) \geq c(\lfloor \frac{n}{2} \rfloor + 1)\lg{(\lfloor \frac{n}{2} \rfloor + 1)}$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} T(n) &=& T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + \Theta(n) \\ &\geq& c(\lceil \frac{n}{2} \rceil + 1)\lg{(\lceil \frac{n}{2} \rceil + 1)} + c(\lfloor \frac{n}{2} \rfloor + 1)\lg{(\lfloor \frac{n}{2} \rfloor + 1)} + \Theta(n) \\ &\geq& c(\frac{n}{2} + 1)\lg{(\frac{n}{2} + 1)} + c(\frac{n - (2 - 1)}{2} + 1)\lg{(\frac{n - (2 - 1)}{2} + 1)} + \Theta(n) \\ &=& c\frac{n + 2}{2}\lg{(n + 2)} + c\frac{n + 1}{2}\lg{(n + 1)} - cn + \Theta(n) - \frac{3c}{2} \\ &>& c\frac{n + 1}{2}\lg{(n + 1)} + c\frac{n + 1}{2}\lg{(n + 1)} - cn + \Theta(n) - \frac{3c}{2} \\ &=& c(n + 1)\lg{(n + 1)} - cn + \Theta(n) - \frac{3c}{2} \\ &\geq& c(n + 1)\lg{(n + 1)} - cn + c_1n - \frac{3c}{2} \\ &=& c(n + 1)\lg{(n + 1)} + (c_1 - c)n - \frac{3c}{2} \\ &>& c(n + 1)\lg{(n + 1)} \\ &>& cn\lg{n} \end{eqnarray} $$

where the last step holds as long as $c < c_1$ and $n \geq \frac{3c}{2(c_1 - c)} $.

So $T(n) = \Theta(n\lg{n})$.

4.3-6

We start by assuming that $T(n) \leq cn\lg{n}$ holds for all positive m < n, in particular for $m = \lfloor \frac{n}{2} \rfloor$, yielding $T(\lfloor \frac{n}{2} \rfloor) \leq c\lfloor \frac{n}{2} \rfloor\lg{\lfloor \frac{n}{2} \rfloor}$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} T(n) &=& 2T(\lfloor \frac{n}{2} \rfloor + 17) + n \\ &\leq& 2c(\lfloor \frac{n}{2} \rfloor + 17)\lg{(\lfloor \frac{n}{2} \rfloor + 17)} + n \\ &\leq& 2c(\frac{n}{2} + 17)\lg{(\frac{n}{2} + 17)} + n \\ &=& c(n + 34)\lg{(n + 34)} + (1 - c)n - 34c \end{eqnarray} $$

It's not easy to prove $T(n) \leq cn\lg{n}$. So we try to guess $T(n) = O((n - k)\lg{(n - k)})$. But we don't know what k is now, substituting into the recurrence yields:

$$ \begin{eqnarray} T(n) &=& 2T(\lfloor \frac{n}{2} \rfloor + 17) + n \\ &\leq& 2c(\lfloor \frac{n}{2} \rfloor + 17 - k)\lg{(\lfloor \frac{n}{2} \rfloor + 17 - k)} + n \\ &\leq& 2c(\frac{n}{2} + 17 - k)\lg{(\frac{n}{2} + 17 - k)} + n \\ &=& c(n + 34 - 2k)\lg{(n + 34 - 2k)} + (1 - c)n + (2k - 34)c \end{eqnarray} $$

Let 34 - 2k = -k, we get k = 34. So $T(n) \leq c(n - 34)\lg{(n - 34)} + (1 - c)n + 34c < c(n - 34)\lg{(n - 34)} < cn\lg{n}$ where the last step holds as long as $c > 1$ and $n \geq \frac{34c}{c - 1}$.

So $T(n) = O(n\lg{n})$.

4.3-7

Here, we have a = 4, b = 3, and $f(n) = \Theta(n)$, and thus we have that $n^{\log_ba} = n^{\log_3{4}}$. Since $n^{\log_3{4}}$ is polynomially larger than f(n) (that is, $f(n) = O(n^{\log_3{4} - \epsilon})$ for $\epsilon \approx 0.2618595071429148$), case 1 applies, and $T(n) = \Theta(n^{\log_3{4}})$.

We start by assuming that this bound holds for all positive m < n, in particular for $m = \frac{n}{3}$, yielding $T(\frac{n}{3}) \leq c(\frac{n}{3})^{\log_3{4}}$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} T(n) &=& 4T(\frac{n}{3}) + n \\ &\leq& 4c(\frac{n}{3})^{\log_3{4}} + n \\ &=& cn^{\log_3{4}} + n \end{eqnarray} $$

So it fails, we cannot prove $T(n) \leq cn^{\log_3{4}}$.

Then let's subtract n from our original guess, let's guess $T(n) \leq cn^{\log_3{4}} - n$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} T(n) &=& 4T(\frac{n}{3}) + n \\ &\leq& 4(c(\frac{n}{3})^{\log_3{4}} - \frac{n}{3}) + n \\ &=& cn^{\log_3{4}} -\frac{n}{3} \\ &<& cn^{\log_3{4}} \end{eqnarray} $$

where the last step holds for all n.

4.3-8

Here, we have a = 4, b = 2, and $f(n) = \Theta(n^2)$, and thus we have that $n^{\log_ba} = n^{\log_2{4}} = n^2$. So case 2 applies, $T(n) = n^2\lg{n}$. But it says it's $\Theta(n^2)$ in the book, so I think it's an error here. If we want to keep the solution to $\Theta(n^2)$, then f(n) should be $n$, not $n^2$. So $T(n) = 4T(\frac{n}{2}) + n$. Since $n^2$ is polynomially larger than f(n) (that is, $f(n) = O(n^{2 - \epsilon})$ for $\epsilon = \frac{1}{2})$, case 1 applies, and $T(n) = \Theta(n^2)$.

We start by assuming that this bound holds for all positive m < n, in particular for $m = \frac{n}{2}$, yielding $T(\frac{n}{2}) \leq c(\frac{n}{2})^2$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} T(n) &=& 4T(\frac{n}{2}) + n \\ &\leq& 4c(\frac{n}{2})^2 + n \\ &=& cn^2 + n \end{eqnarray} $$

So we cannot prove $T(n) \leq cn^2$.

Then let's subtract n from our original guess, let's guess $T(n) \leq cn^2 - n$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} T(n) &=& 4T(\frac{n}{2}) + n \\ &\leq& 4(c(\frac{n}{2})^2 - \frac{n}{2}) + n \\ &=& cn^2 -n \\ &<& cn^2 \end{eqnarray} $$

where the last step holds for all n.

4.3-9

Renaming $m = \lg{n}$ yields $T(2^m) = 3T(2^{\frac{m}{2}}) + m$. We can new rename $S(m) = T(2^m)$ to produce the new recurrence $S(m) = 3S(\frac{m}{2}) + m$.

We start by assuming that $S(n) \leq cm\lg{m}$ holds for all positive p < m, in particular for $p = \frac{m}{2}$, yielding $S(\frac{m}{2}) \leq c\frac{m}{2}\lg{\frac{m}{2}}$. Substituting ino the recurrence yields:

$$ \begin{eqnarray} S(m) &=& 3S(\frac{m}{2}) + m \\ &\leq& 3c\frac{m}{2}\lg{\frac{m}{2}} + m \\ &=& \frac{3c}{2}m\lg{m} + (1 - \frac{3c}{2})m \end{eqnarray} $$

It's not easy to prove $\frac{3c}{2}m\lg{m} + (1 - \frac{3c}{2})m \leq cm\lg{m}$, so let's try to guess $S(m) \leq c\frac{2m}{3}\lg{m}$. So:

$$ \begin{eqnarray} S(m) &\leq& 3c\frac{m}{3}\lg{\frac{m}{2}} + m \\ &=& cm\lg{m} + (1 - c)m \\ &\leq& cm\lg{m} \end{eqnarray} $$

where the last step holds as long as $c \geq 1$.

So $S(m) = O(m\lg{m})$, so $T(n) = O(\lg{n}\lg{\lg{n}})$.