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)?
Problem 3
Draw a recursion tree diagram for $$ T(n)= \begin{cases}9 T(n / 3)+n & \text { if } n>1 \\ 1 & \text { if } n=1\end{cases} $$ Use it to find a big \(\Theta\) bound on the solution to the recurrence. Assume \(n\) is a power of 3 .
Problem 4
Draw a recursion tree diagram for $$ T(n)= \begin{cases}T(n / 4)+n & \text { if } n \geq 2, \\ 1 & \text { if } n=1 .\end{cases} $$ Use it to find a big \(\Theta\) bound to the solution to the recurrence. Assume \(n\) is a power of \(4 .\)
Problem 4
Prove that \(1^{3}+2^{3}+3^{3}+\cdots+n^{3}=n^{2}(n+1)^{2} / 4\).
Problem 4
Give a big \(\Theta\) bound on the solution to the recurrence $$ T(n)= \begin{cases}3 T(\lceil n / 2\rceil)+\sqrt{n^{4}+3} & \text { if } n>1 \\\ d & \text { if } n=1\end{cases} $$
Problem 5
Draw a recursion tree diagram for $$ T(n)= \begin{cases}2 T(n / 4)+n & \text { if } n \geq 2 \\ 1 & \text { if } n=1\end{cases} $$ Use it to find a big \(\Theta\) bound on the solution to the recurrence. Assume \(n\) is a power of 4 .
Problem 5
Find a big \(\Theta\) bound (the best you know how to get) on solutions to the recurrence \(T(n)=T(n / 3)+T(n / 6)+T(n / 4)+n\), with \(T(1)=1\).
Problem 5
Give a big \(\Theta\) bound on the solution to the recurrence $$ T(n)= \begin{cases}2 T(\lceil n / 2\rceil)+\sqrt{n^{2}+3} & \text { if } n>1 \\\ d & \text { if } n=1\end{cases} $$
Problem 6
Find a big \(\Theta\) bound to solutions to the recurrences \(T(n / 4)+T(3 n / 4)+d n \leq T(n) \leq T(n / 4)+T(3 n / 4)+c n .\)
Problem 6
a. Find the best big \(O\) upper bound you can to any solution to the recurrence $$ T(n)= \begin{cases}4 T(n / 2)+n \log n & \text { if } n>1 \\ 1 & \text { if } n=1\end{cases} $$ b. Assuming that you were able to guess the result you got in part a, prove by induction that your answer is correct.
