Problem 8
Draw a recursion tree diagram for \(T(n)=T(n / 3)+1\), with \(T(1)=3\). Use it to find an exact solution to the recurrence.
Problem 9
Our arguments in favor of the sum principle were quite intuitive. In fact, the sum principle for \(n\) sets follows from the sum principle for two sets. Use induction to prove the sum principle for a union of \(n\) sets from the sum principle for a union of two sets.
Problem 9
Consider the recurrence \(T(n)=3 T(n-1)+1\), with the initial condition \(T(0)=2\). You could write the solution from Theorem 4.1. Instead of using the theorem, try to guess the solution from the first four values of \(T(n)\) and then try to guess the solution by iterating the recurrence four times.
Problem 9
Draw recursion trees, and use them to find big \(\Theta\) bounds on the solutions to the following recurrences. For each, assume that \(T(1)=1\) and that \(n\) is a power of the appropriate integer. a. \(T(n)=8 T(n / 2)+n\) b. \(T(n)=8 T(n / 2)+n^{3}\) c. \(T(n)=3 T(n / 2)+n\) d. \(T(n)=T(n / 4)+1\) e. \(T(n)=3 T(n / 3)+n^{2}\)
Problem 10
Give the best big \(O\) upper bound you can for the solution to the recurrence $$ T(n)=2 T\left(\frac{n}{3}-3\right)+n $$ (making an informed guess is not a bad idea here). Then prove by induction that your upper bound is correct.
Problem 10
Draw recursion trees and find exact solutions to the following recurrences. For each, assume that \(T(1)=1\) and that \(n\) is a power of the appropriate integer. a. \(T(n)=8 T(n / 2)+n\) b. \(T(n)=8 T(n / 2)+n^{3}\) c. \(T(n)=3 T(n / 2)+n\) d. \(T(n)=T(n / 4)+1\) e. \(T(n)=3 T(n / 3)+n^{2}\)
Problem 10
What sort of big \(\Theta\) bound can you give on the value of a geometric series \(1+r+r^{2}+\cdots+r^{n}\), with common ratio \(r=1 ?\)
Problem 11
Find the error in the following "proof" that all positive integers \(n\) are equal: Let \(p(n)\) be the statement that all numbers in an \(n\)-element set of positive integers are equal. Then \(p(1)\) is true. Now assume \(p(n-1)\) is true, and let \(N\) be the set of the first \(n\) integers. Let \(N^{\prime}\) be the set of the first \(n-1\) integers, and let \(N^{\prime \prime}\) be the set of the last \(n-1\) integers. By \(p(n-1)\), all members of \(N^{\prime}\) are equal, and all members of \(N^{\prime \prime}\) are equal. Thus, the first \(n-1\) elements of \(N\) are equal and the last \(n-1\) elements of \(N\) are equal, and so all elements of \(N\) are equal. Therefore, all positive integers are equal.
Problem 11
Solve the recurrence \(T(n)=2 T(n-1)+n 2^{n}\), with the initial condition \(T(0)=1\).
Problem 11
Find the best big \(O\) upper bound you can to any solution to the recurrence defined on nonnegative integers by $$ T(n) \leq 2 T\left(\left[\frac{n}{2}\right]+1\right)+c n . $$ (There is nothing wrong with informed guesswork.) Prove by induction that your answer is correct.
