Consider the following recurrence T(n): T(n) = = { if n = 1 2T([])+16 if n>1...

  

Transcribed Image Text:

Consider the following recurrence T(n): T(n) = = { if n = 1 2T([])+16 if n>1 (3 points) 1. Use the recursion tree or repeated substitution method to come up with a good guess for a bound g(n) on the recurrence T(n). (2 points) 2. State and prove by induction a theorem showing T(n) = (g(n)). Consider the following recurrence T(n): T(n) = { C if n = 1 if n > 1 T([])+T([])+4n (1 point) 3. Draw the first six levels of the recursion tree by drawing all recursive calls of the same size on the same level. Make sure on each level you indicate the size of the recursive call and the number of recursive calls. (1 point) 4. Express the cost of all levels of the recursion tree as a sum over the cost of each level of the recursion tree. (1 point) 5. Give a function g(n) and show it is an upper bound on the sum. (2 points) 6. State and prove by induction a theorem showing T(n) (g(n)). Consider the following recurrence T(n): T(n) = = { if n = 1 2T([])+16 if n>1 (3 points) 1. Use the recursion tree or repeated substitution method to come up with a good guess for a bound g(n) on the recurrence T(n). (2 points) 2. State and prove by induction a theorem showing T(n) = (g(n)). Consider the following recurrence T(n): T(n) = { C if n = 1 if n > 1 T([])+T([])+4n (1 point) 3. Draw the first six levels of the recursion tree by drawing all recursive calls of the same size on the same level. Make sure on each level you indicate the size of the recursive call and the number of recursive calls. (1 point) 4. Express the cost of all levels of the recursion tree as a sum over the cost of each level of the recursion tree. (1 point) 5. Give a function g(n) and show it is an upper bound on the sum. (2 points) 6. State and prove by induction a theorem showing T(n) (g(n)).