Problem 2. Recursion Tree (10 points) Consider the following recurrence: T(n)=3T(n/4)+T(n/8)+n? T(1) = C Solve this...

Transcribed Image Text:

Problem 2. Recursion Tree (10 points) Consider the following recurrence: T(n)=3T(n/4)+T(n/8)+n? T(1) = C Solve this recurrence with a recursion tree. That is find a function f(n) (whose specification does not involve a recurrence) such that T(n) = O(f(n)). To do this, start by examining the first tree levels of the recursion tree, showing how to compute the amount of work at each level. From here, establish a formula for the amount of work on level i. Then, determine the last level of the recursion tree. Finally, construct a summation which totals the amount of work over all levels and show why this summation is O(f(n)). Your f(n) should follow directly from your analysis. You are welcome to embed a photo of a hand drawn image into your LaTeX file. Problem 2. Recursion Tree (10 points) Consider the following recurrence: T(n)=3T(n/4)+T(n/8)+n? T(1) = C Solve this recurrence with a recursion tree. That is find a function f(n) (whose specification does not involve a recurrence) such that T(n) = O(f(n)). To do this, start by examining the first tree levels of the recursion tree, showing how to compute the amount of work at each level. From here, establish a formula for the amount of work on level i. Then, determine the last level of the recursion tree. Finally, construct a summation which totals the amount of work over all levels and show why this summation is O(f(n)). Your f(n) should follow directly from your analysis. You are welcome to embed a photo of a hand drawn image into your LaTeX file.

Answer rating: 100% (QA)

To solve this recurrence with a recursion tree we will analyze the amount of work done at each level ... View the full answer