CSE 247 Module 5: Recurrences II
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.
Thanks to Marc Moreno Maza for the following problems. The TAs have the
solutions if you want to check your answers.
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.
determine for each of the recurrences below:
- If the
applies, state the solution to the recurrence according to the theorem.
- If the
does not apply, state why.
At each horizontal line below, check your answers so far with other groups or with the TA.
- T(n) = 3T(n/2) + n2
- T(n) = 4T(n/2) + n2
- T(n) = T(n/2) + 2n
- T(n) = 2nT(n/2) + nn
- T(n) = 16T(n/4) + n
- T(n) = 2T(n/2) + n log n
- T(n) = 2T(n/2) + n / log n
- T(n) = 2T(n/4) + n0.51
- T(n) = 0.5T(n/2) + 1 / n
- T(n) = 16T(n/4) + n!
- T(n) =
T(n/2) + log n
- T(n) = 3T(n/2) + n
- T(n) = 3T(n/3) +
- T(n) = 4T(n/2) + c n
- T(n) = 3T(n/4) + n log n
- T(n) = 3T(n/3) + n / 2
- T(n) = 6T(n/3) + n2 log n
- T(n) = 4T(n/2) + n / log n
- T(n) = 64T(n/8) - n2 log n
- T(n) = 7T(n/3) + n2
- T(n) = 4T(n/2) + log n
Review Using Old Exams
Here are the old exams:
them 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)
- 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.
- Follow the instructions in the green box below to receive credit for your work.
Last modified 14:14:21 CST 01 December 2016
When you done with this studio, you must be cleared by the TA to receive credit.
- Commit all your work to your repository
- Fill in the form below with the relevant information
- Have a TA check your work
- The TA should check your work and then fill in his or her name
- Click OK while the TA watches
- If you request propagation, it does not happen immediately,
but should be posted in the next day or so
This demo box is for studio 5