example of format for substitution method:

1. (15 pts) For the following recurrence, T(n) = 0 n = 1 T(n) = 4T(n-1) + C n >1 a. Solve the recurrence using the recursion tree method. Give the solution in big-o notation. Show your work in sufficient details. b. Use the substitution method to prove your above solution is correct. Show your work in sufficient details. Solving Recurrences with the Substitution Method (two steps): o Guess a solution Show the solution is correct by inductive proof. 1. Solve T(n) = c for n = 1 and T(n) = 2T(n/2) + cn for n> 1 using substitution. Guess: T(n) = O(nlgn). (We want to make a good guess - Is it a good guess?) Proof by Induction: 1) Goal: 2) Inductive Proof: Inductive Hypo: So far the restrictions (on C and no) are: 3) Base case