Skip to content

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:

Recursion 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:

Recursion 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:

Recursion 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:

Recursion 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)