CSE 247 Module 4: Recurrences I


Be sure to do a TeamPull to update your repositories.


Write your proofs as text in the studio4.text file of the studiowriteups folder.

Recursion Trees

Consider each of the following recurrences and initial values:
Recurrence Initial value Solution
If you need it
Ask the TA for the password
1. T(n) = T(n-1) + 2n - 1 T(0) = 10 solution ]
2. T(n) = T(n-1) + 4n - 5 T(0) = 5 solution ]
3. T(n) = T(n/5) + 7 T(0) = 21 solution ]
4. T(n) = 4T(n/2) + 2n T(0) = 0 solution ]

For each recurrence:

Document your findings in the studio4.txt file of the studiowriteups folder of your repository.

If you need help with lab 3, please use time in studio to get help once you have worked on the above problems to the satisfaction of your TA.

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 4
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: