CSE 247 Module 5: Recurrences II

Studio

There is no studio5.txt file for you to complete this time. You should do this work on paper that you can take away with you.

Material I have shown you:

You may also find the Wikipedia page on the Master Method helpful. Its version is slightly more general for case 2 than what I presented.
Thanks to Marc Moreno Maza for the following problems. The TAs have the solutions if you want to check your answers.

Using the Master Theorem, determine for each of the recurrences below:

• If the Master Theorem applies, state the solution to the recurrence according to the theorem.
• If the Master Theorem does not apply, state why.

Recurrences

At each horizontal line below, check your answers so far with other groups or with the TA.
1. T(n) = 3T(n/2) + n2
2. T(n) = 4T(n/2) + n2
3. T(n) = T(n/2) + 2n
4. T(n) = 2nT(n/2) + nn
5. T(n) = 16T(n/4) + n
6. T(n) = 2T(n/2) + n log n
7. T(n) = 2T(n/2) + n / log n
8. T(n) = 2T(n/4) + n0.51
9. T(n) = 0.5T(n/2) + 1 / n
10. T(n) = 16T(n/4) + n!
11. T(n) =  2  T(n/2) + log n
12. T(n) = 3T(n/2) + n
13. T(n) = 3T(n/3) +  n
14. T(n) = 4T(n/2) + c n
15. T(n) = 3T(n/4) + n log n
16. T(n) = 3T(n/3) + n / 2
17. T(n) = 6T(n/3) + n2 log n
18. T(n) = 4T(n/2) + n / log n
19. T(n) = 64T(n/8) - n2 log n
20. T(n) = 7T(n/3) + n2
21. T(n) = 4T(n/2) + log n

Review Using Old Exam I

Here is the Exam I from last semester. Go over it in your group and see how well you do. The TAs don't have answers, but can help you if you get stuck.

• If there is a file for you to complete in studiowriteups, please respond to the questions and supply any requested information.
• You must commit and push all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.