

Week 4 - Recurrences

Notes

Master Theorem

$T(n) = aT(\dfrac{n}{b}) + f(n)$, where $a \geq 1, b > 1$, then

$$\begin{align*} T(n) = \begin{cases} &\Theta(n^{\lg_b a}) &\text{, where } f(n) = o(n^{\lg_b a}) \\\\ &\Theta(n^{\lg_b a}\lg n) &\text{, where } f(n) = \Theta(n^{\lg_b a}) \\\\ &\Theta(f(n)) &\text{, where } f(n) = \omega(n^{\lg_b a}) \textbf{ and } af(n/b) = O(f(n)) \end{cases} \end{align*}$$

Assignment - Due 10/20/2018

Credit: source code of questions are from walkccc.

4.3-6

Show that the solution to $T(n) = 2T(\lfloor n / 2 \rfloor + 17) + n$ is $O(n\lg n)$.

Suppose that $T(n) = O(\lg n)$, then $\exists c>0$, letting

$$\begin{align*} T(n) = &2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor+17) + n \leq c(n-34)\lg(n-34)\\ T(n) = &2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor+17) + n\\ &\leq 2T(\dfrac{n}{2}+17) + n\\ &\leq 2c(\dfrac{n}{2}+17-34)\log(\dfrac{n}{2}+17-34) + n\\ &= c(n-34)(\lg(n-34) - \lg2) + n\\ &= c(n-34)\lg(n-34) - c(n-34) + n\\ &\leq c(n-34)\lg(n-34)\\ c&\geq \dfrac{n}{n-34} = 35\text{ }(n_0 = 35) \end{align*}$$

So when $c \geq 35, n_0 = 35$, the inequality holds, which is

$$T(n) = 2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor+17) + n = O(\lg n)$$

4.3-7

Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n / 3) + n$ is $T(n) = \Theta(n^{\log_3 4})$. Show that a substitution proof with the assumption $T(n) \le cn^{\log_3 4}$ fails. Then show how to subtract off a lower-order term to make the substitution proof work.

If we suppose that $\exists{c>0}$ letting $T(n) = 4T(\dfrac{n}{3}) + n \leq cn^{\log_3{4}}$:

$$\begin{align*} T(n) &= 4T(\dfrac{n}{3}) + n\\ &\leq 4c\times(\dfrac{n}{3})^{\log_3{4}} + n\\ &= cn^{\log_3{4}} + n\\ &\leq cn^{\log_3{4}} \end{align*}$$

But this lead to $n \leq 0$, which is impossible, the substitution proof above fails. Instead, if we suppose $\exists{c>0}$, letting $T(n) = 4T(\dfrac{n}{3}) + n \leq cn^{\log_3{4}} - dn$:

$$\begin{align*} T(n) &= 4T(\dfrac{n}{3}) + n\\ &\leq 4(c\times(\dfrac{n}{3})^{\log_3{4}} - d(\dfrac{n}{3})) + n\\ &= cn^{\log_3{4}} - \dfrac{4d}{3}n + n\\ &\leq cn^{\log_3{4}} - dn\\ d&\geq 3 \end{align*}$$

So when $c>0, d \geq 3$, the inequality holds, which is

$$T(n) = 4T(\dfrac{n}{3}) + n = \Theta(n^{\log_3{4}})$$

4.3-8

Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n / 2) + n^2$ is $T(n) = \Theta(n^2)$. Show that a substitution proof with the assumption $T(n) \le cn^2$ fails. Then show how to subtract off a lower-order term to make the substitution proof work.

If we suppose that $\exists{c>0}$, letting $4T(\dfrac{n}{2}) + n^2 \leq cn^2$:

$$\begin{align*} T(n) &= 4T(\dfrac{n}{2}) + n^2\\ &\leq 4c\times(\dfrac{n}{2})^2 + n^2\\ &= cn^2 + n^2\\ &\leq cn^2 \end{align*}$$

Dead end!

In fact, according to Master Theorem, the asymptotic bound of $T(n)$ is $\Theta(n^2\lg n)$. Suppose $\exists c>0, \exists d>0$, letting $4T(\dfrac{n}{2}) + n^2 \leq cn^2\lg n - dn$:

$$\begin{align*} T(n) &= 4T(\dfrac{n}{2}) + n^2\\ &\leq 4(c\times(\dfrac{n}{2})^2\lg{(\dfrac{n}{2})} - d(\dfrac{n}{2}))+ n^2\\ &= cn^2\lg{n} - cn^2 - 2dn + n^2\\ &\leq cn^2\lg{n} - dn\\ c&\geq 1 \end{align*}$$

So when $c \geq 1, d > 0, T(n) = O(n^2\lg n)$.

Similarly, we can prove $T(n) = \Omega(n^2\lg n)$. which is

$$T(n) = 4T(\dfrac{n}{2}) + n^2 = \Theta(n^2\lg n)$$

4.3-9

Solve the recurrence $T(n) = 3T(\sqrt n) + \log n$ by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

Since $T(n) = 3T(\sqrt{n}) + \lg{n}$, let $n = 2^k$, then

$$T(2^k) = 3T(2^\frac{k}{2}) + k$$

Let $S(k) = T(2^k)$, then

$$S(k) = 3S(\dfrac{k}{2}) + k$$

According to Master Theorem, we can suppose

$$S(k) = \Theta(k^{\lg{3}})$$

then $\exists c > 0, \exists d > 0, \exists e > 0, \exists f > 0$ letting

$$ck^{\lg{3}} + dk\leq S(k) \leq ek^{\lg{3}} - fk$$

$$\begin{align*} S(k) &= 3S(\dfrac{k}{2}) + k &S(k)&= 3S(\dfrac{k}{2}) + k\\ &\leq 3(e(\dfrac{k}{2})^{\lg{3}}-f\dfrac{k}{2})+k& &\geq 3(c(\dfrac{k}{2})^{\lg{3}}+d\dfrac{k}{2})+k\\ &= ek^{\lg{3}} + \frac{2-3f}{2}k & &= ck^{\lg{3}} + \frac{2+3d}{2}k\\ &\leq ek^{\lg{3}} - fk & &\geq ck^{\lg{3}} + dk\\ f&\geq 2 & d&\geq -2\text{ ($d>0$)} \end{align*}$$

So, when $c>0, d > 0, e>0, f\geq 2, S(k) = \Theta(k^{\lg3})$, which is

$$T(n) = S(\lg n) = \Theta(\lg^{\lg3}{n})$$

4.4-1

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 3T(\lfloor n / 2 \rfloor) + n$. Use the substitution method to verify your answer.

Suppose $n$ is exact power of 2, we can draw the tree:

• At level $i$, the size is $\dfrac{n}{2^i}$, and the number of nodes is $i$ is $3^i$, so the cost is

$$3^i \times \dfrac{n}{2^i} = (\dfrac{3}{2})^i{n}$$

• Specifically, the size at the last level is 1, so the number of levels is $\lg n$, and the cost is:

$$3^{\lg{n}} \times 1 = n^{\lg{3}} = \Theta{(n^{\lg{3}})}$$

The total cost of the tree is:

$$\begin{align*} T(n) &= \sum_{i=0}^{\lg{n}-1} (\dfrac{3}{2})^i{n} + \Theta{(n^{\lg{3}})}\\ &\leq \frac{(\frac{3}{2})^{\lg{n}-1+1}-1}{\frac{3}{2}-1}n + \Theta{(n^{\lg{3}})}\\ &= 2n(\dfrac{3}{2})^{\lg{n}}-1) + \Theta{(n^{\lg{3}})}\\ &= 2n(n^{\lg{\frac{3}{2}}}-1) + \Theta{(n^{\lg{3}})}\\ &= 2(n^{\lg3}-n) + \Theta{(n^{\lg{3}})}\\ &= O(n^{\lg3}) \end{align*}$$

We use substitution to prove the conclusion above is right. Suppose $T(n) = O(n^{\lg3})$, $\exists c>0, \exists d>0$ letting

$$\begin{align*} T(n) &= 3T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + n \\ &\leq cn^{\lg3} - dn\\ \\ T(n) &= 3T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + n\\ &\leq 3T(\dfrac{n}{2}) + n\\ &\leq 3c(\dfrac{n}{2})^{\lg3} - \dfrac{3d}{2}n + n\\ &= cn^{\lg3} - \dfrac{3d}{2}n + n\\ &\leq cn^{\lg3} - dn\\ d&\geq 2 \end{align*}$$

So, when $c>0, d \geq 2$, $T(n) = O(n^{\lg3})$.

4.4-2

Use a reccursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = T(n / 2) + n^2$. Use the substitution method to verify your answer.

Suppose $n$ is exact power of 2, we can draw the tree:

• At level $i$, the size is $\dfrac{n}{2^i}$, and the number of nodes is $i$, so the cost is $\dfrac{n^2}{4^i}$.
• Specifically, the size at the last level is 1, so the number of levels is $\lg n$, and the cost is 1. So the total cost of the tree is:

$$\begin{align*} T(n) &= \sum_{i=0}^{\lg{n}-1} (\dfrac{1}{4})^i{n^2} + 1\\ &\leq \sum_{i=0}^{+\infty} (\dfrac{1}{4})^i{n^2} + 1\\ &= \dfrac{1}{1 - 1/4}n^2 + 1\\ &= O(n^2) \end{align*}$$

We use substitution to prove the conclusion above is right. Suppose $T(n) = O(n^2)$, $\exists c>0$ letting $T(n) \leq cn^2$:

$$\begin{align*} T(n) &= T(\dfrac{n}{2}) + n^2\\ &\leq c(\dfrac{n}{2})^2 + n^2\\ &= (1 + \dfrac{c}{4})n^2\\ &\leq cn^2\\ c&\geq \dfrac{4}{3} \end{align*}$$

Thus the inequality holds, $T(n) = O(n^2)$.

4.4-3

Use a reccursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 4T(n / 2 + 2) + n$. Use the substitution method to verify your answer.

We can make a good guess by looking into $T(n) = 4T(n / 2 + 2) + n$ instead. Suppose $n$ is exact power of 2, we can draw the tree:

• At level $i$, the size is $\dfrac{n}{2^i}$, and the number of nodes is $4^i$, so the cost is $4^i \cdot \dfrac{n}{2^i} = 2^i{n}$.

• Specifically, the size at the last level is 1, so the number of levels is $\lg n$, and it has $n^2$ leaves. The total cost of the tree is:

$$\begin{align*} T(n) &= \sum_{i=0}^{\lg{n}-1} 2^i{n} + n^2\\ &= \frac{2^{\lg n}-1}{2-1} + n^2\\ &= n^2 + n - 1\\ &= O(n^2) \end{align*}$$

We use substitution to prove the conclusion above is right. Suppose $T(n) = O(n^2)$, $\exists c>0, \exists d>0$ letting $T(n) \leq cn^2 - dn$:

$$\begin{align*} T(n) &= 4T(\dfrac{n}{2} + 2) + n\\ &\leq 4(c(\dfrac{n}{2} + 2)^2 - d(\dfrac{n}{2} + 2)) + n\\ &= 4(c(\dfrac{n}{2} + 2)^2 - d(\dfrac{n}{2} + 2)) + n\\ &= cn^2 + (8c-2d+1)n + 16c-8d\\ &\leq cn^2 - dn\\ c&> 0, d \geq 8c + 1 \end{align*}$$

Thus the inequality holds, $T(n) = O(n^2)$.

4.4-4

Use a reccursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 2T(n - 1) + 1$. Use the substitution method to verify your answer.

We can draw the tree:

• At level $i$, the size is $(n-i)$, and the number of nodes is $2^i$, and the cost is $2^i$.
• Specifically, the size at the last level is 1, so the number of levels is $2^n$. The total cost of the tree is:

$$\begin{align*} T(n) &= \sum_{i=0}^{n-1} 2^i + 2^n\\ &\leq \sum_{i=0}^{n-1} 2^i + 2^n\\ &= \frac{2^n-1}{2-1} + 2^n\\ &= O(2^n) \end{align*}$$

We use substitution to prove the conclusion above is right. Suppose $T(n) = O(2^n)$, $\exists c>0, \exists d>0$ letting $T(n) \leq c2^n - d$:

$$\begin{align*} T(n) &= 2T(n-1) + 1\\ &\leq 2(c2^{n-1} - d) + 1\\ &= c2^n - 2d + 1\\ &\leq c2^n - d\\ c&> 0, d \geq \dfrac{1}{2} \end{align*}$$

Thus the inequality holds, $T(n) = O(2^n)$.

4.4-5

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = T(n - 1) + T(n / 2) + n$. Use the substitution method to verify your answer.

This is an unbalance tree, and its scale is between $T(n) = 2T(\dfrac{n}{2}) + n$ and $T(n) = 2T(n-1) + n$. So guess $T(n) = O(2^n)$, $\exists a>0, \exists b>0$ letting $T(n) \leq a2^n-bn$:

$$\begin{align*} T(n) &= T(n-1) + T(\dfrac{n}{2}) + n\\ &\leq a2^{n-1}-b(n-1) + a2^{\frac{n}{2}}-b\dfrac{n}{2} + n\\ &= a(2^{n-1} + 2^{\frac{n}{2}}) + (1-\dfrac{3}{2}b)n + b\\ &\leq a(2^{n-1} + 2^{n-1}) + (1-\dfrac{3}{2}b)n + b\text{ ($n\geq 2$)}\\ &\leq a2^n-bn\\ a &> 0, b > 2, n_0 = 2 \end{align*}$$

Thus the inequality holds, $T(n) = O(2^n)$.

4.5-1

Use the master method to give tight asymptotic bounds for the following recurrences:

a. $T(n) = 2T(n / 4) + 1$.

b. $T(n) = 2T(n / 4) + \sqrt n$.

c. $T(n) = 2T(n / 4) + n$.

d. $T(n) = 2T(n / 4) + n^2$.

a. $\Theta(n^{\lg_4 2}) = \omega(1) \Rightarrow \Theta(\sqrt{n})$

b. $\Theta(n^{\lg_4 2}) = \Theta(\sqrt{n}) \Rightarrow \Theta(\sqrt{n}\lg n)$

c. $\Theta(n^{\lg_4 2}) = o(n) \Rightarrow \Theta(n)$

d. $\Theta(n^{\lg_4 2}) = o(n^2) \Rightarrow \Theta(n^2)$