## 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.
- T(n) = 3T(n/2) + n
^{2}
- T(n) = 4T(n/2) + n
^{2}
- T(n) = T(n/2) + 2
^{n}
- T(n) = 2
^{n}T(n/2) + n^{n}

- 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) + n
^{0.51}

- T(n) = 0.5T(n/2) + 1 / n
- T(n) = 16T(n/4) + n!
- T(n) =
√ 2
T(n/2) + log n
- T(n) = 3T(n/2) + n

- T(n) = 3T(n/3) +
√ n
- 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) + n
^{2} log n
- T(n) = 4T(n/2) + n / log n
- T(n) = 64T(n/8) - n
^{2} log n
- T(n) = 7T(n/3) + n
^{2}
- 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)

- 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:54:20 CDT 31 October 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**