Problem 1
Suppose that \(c\) is a real number greater than 0 . Show by induction that any solution \(T(n)\) to the recurrence $$ T(n) \leq T\left(\frac{n}{4}\right)+c n $$ with \(n\) restricted to integer powers of 4 , has \(T(n)=O(n)\).
Problem 1
Find the best big \(O\) bound you can on \(T(n)\) if it satisfies the recurrence \(T(n) \leq T(n / 4)+T(n / 2)+n\), with \(T(n)=1\) if \(n<4\).
Problem 1
Use the master theorem to give 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 1
This problem explores ways to prove that $$ \frac{2}{3}+\frac{2}{9}+\cdots+\frac{2}{3^{n}}=1-\left(\frac{1}{3}\right)^{n} $$ for all positive integers \(n\). a. First, we explore how to prove the formula by contradiction. In other words, assume that there is some integer \(n\) that makes the formula false. In this case, there must be some smallest \(n\) that makes the formula false. i. Can this smallest \(n\) be \(1 ?\) ii. What do you know about $$ \frac{2}{3}+\frac{2}{9}+\cdots+\frac{2}{3^{i}} $$ when \(i\) is a positive integer smaller than this smallest \(n\) ? iii. Is \(n-1\) a positive integer for this smallest \(n\) ? iv. What do you know about $$ \frac{2}{3}+\frac{2}{9}+\cdots+\frac{2}{3^{n-1}} $$ for this smallest \(n\) ? v. Write the answer to part iv as an equation, add \(2 / 3^{n}\) to both sides, and simplify the right side. vi. What does the equation that results from part \(\mathrm{v}\) say about your assumption that the formula is false? vii. What can you conclude about the truth of the formula? viii. If \(p(k)\) is the statement $$ \frac{2}{3}+\frac{2}{9}+\cdots+\frac{2}{3^{k}}=1-\left(\frac{1}{3}\right)^{k} $$ what implication did you prove in the process of deriving your contradiction? b. i. What is the base case in a proof by mathematical induction that $$ \frac{2}{3}+\frac{2}{9}+\cdots+\frac{2}{3^{n}}=1-\left(\frac{1}{3}\right)^{n} $$ for all positive integers \(n\) ? ii. What would you assume as an inductive hypothesis? iii. What would you prove in the inductive step of a proof of this formula by induction? iv. Prove it. v. What does the principle of mathematical induction allow you to conclude? vi. If \(p(k)\) is the statement $$ \frac{2}{3}+\frac{2}{9}+\cdots+\frac{2}{3^{k}}=1-\left(\frac{1}{3}\right)^{k} $$ what implication did you prove in the process of doing your proof by induction?
Problem 1
Draw a recursion tree diagram for $$ T(n)= \begin{cases}4 T(n / 4)+n & \text { if } n \geq 2, \\ 1 & \text { if } n=1 .\end{cases} $$ Use it to find the exact solution to the recurrence. Assume \(n\) is a power of \(4 .\)
Problem 2
Use contradiction to prove $$ 1 \cdot 2+2 \cdot 3+\cdots+n(n+1)=n(n+1)(n+2) / 3 \text {. } $$
Problem 2
Give a big \(\Theta\) bound on the solution to the recurrence $$ T(n)= \begin{cases}3 T(\lceil n / 2\rceil)+\sqrt{n+3} & \text { if } n>1 \\ d & \text { if } n=1\end{cases} $$
Problem 2
Prove by induction that if \(T(n) \leq 4 T(n / 2)+n^{2}\), then \(T(n)=O\left(n^{2} \log n\right)\) (assuming \(n\) is a power of 2 ).
Problem 2
Draw a recursion tree diagram for $$ T(n)= \begin{cases}2 T(n / 2)+2 n & \text { if } n \geq 2 \\ 2 & \text { if } n=1\end{cases} $$ Use it to find the exact solution to the recurrence. Assume \(n\) is a power of \(2 .\)
Problem 3
Show by induction that any solution to a recurrence of the form $$ T(n) \leq 2 T\left(\frac{n}{3}\right)+c \log _{3} n $$ is \(O\left(n \log _{3} n\right)\). What happens if you replace 2 with 3 ? Explain why. Would it make a difference if you used a different base for the logarithm (only an intuitive explanation is needed here)?
