## CSE 247 Module 4: Recurrences I

### Studio

Be sure to do a TeamPull to update your repositories.

### Substitution

• Using substitution, prove that the solution to T(n)=T(n-1)+10 is T(n)=10n
• Using substitution, show that T(n)=T(n-1)+10 is O(n2).
It may help to review this example from lecture. It may take a while for the link to resolve to the slide; be patient please.
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:
Problem
Number
Recurrence Initial value Solution
If you need it
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:

• Find and open the Excel spreadsheet corresponding to the problem, such as Prob1.xlsx for problem 1. You'll find these in the studio4 package of the studios source folder.
Here is what you will see in the sheet (using Prob1.xlsx as our example):  Column A is n, the parameter for the recurrence. Column B is the location of the recurrent term. This will change from sheet to sheet, depending on the recurrence formula. Column C is the value computed by the recurrence itself. This involves referencing the value of the recurren term and evaluating the right-hand side of the recurrence formula. You should not change any of the above columns' contents! Column D is where you will do your work, comparing the results you get there with Column C. They should agree exactly (in some rows, but maybe not all) when you have the right answer. Initially, there is some function in Column D that is certainly not the right answer, but whose values are plotted. The plot shows Columns C and D as a function of Column A. As you change Column D, the plot will change too.
• Sketch the recursion tree.
• Use the recursion tree to sum the costs of computing T(n)
• What function is currently modeled in column D of your spreadsheet?
• Try your closed formula in column D of the Excel spreadsheet
• If you're right it should agree with what you see in Column C
• It may help to review these slides from lecture on recursion trees.
• The example of this I did in class can be found in the PersianRecursion.xlsx file in the lecture4 package of your lectures source folder.
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.

• 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.