Question 5: Divide-and-Conquer and Recurrences (10 points] (a) A divide-and-conquer algorithm divides a problem of size

[answerhappygod]

Question 5 Divide And Conquer And Recurrences 10 Points A A Divide And Conquer Algorithm Divides A Problem Of Size 1 (123.75 KiB) Viewed 27 times

Question 5: Divide-and-Conquer and Recurrences (10 points] (a) A divide-and-conquer algorithm divides a problem of size n into 2 sub-problems, each of size n/4. The divide time is 5n and the combine time is constant. 1. Write a recurrence that expresses the algorithm's running time. (1 point) 2. What's the algorithm's recursion depth? Give the exact value not the asymptotic value. (1 point) 3. Solve the recurrence using the Master Theorem. Show all steps for full credit (2 points) (b) Given the following code for computing the nth Fibonacci number: Fib (n) If nr=0 or n == 1 return n Return Fib(n-1) + Fib(n-2) 1. Write a recurrence that represents the algorithm's running time. Clearly show what the divide and combine times are in your recurrence. (2 points) 2. Use the recursion-tree method to solve the recurrence that you wrote in Part 1 for the Fibonacci algorithm. Indicate the tightness of the bound that you compute using the asymptotic notation (e, o, etc.). For full credit, draw the tree and show all steps. (4 points)