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:

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.

Submitting your work (read carefully)



Last modified 14:54:20 CDT 31 October 2016
When you done with this studio, you must be cleared by the TA to receive credit.

This demo box is for studio 5
Last name WUSTL Key Propagate?
(NOT your numeric ID) Do not propagate
e.g. Smith j.smith
1 Copy from 1 to all others
2 Copy from 2 to all others
3 Copy from 3 to all others
4 Copy from 4 to all others

TA: Password: