Problem 5: Recursion (10 points) Here are two algorithms to compute 2" for any integer n >= 0. Algi (n) Alg2 (n) if n = 0 return 1 else return 2 * Algi (n-1) if n == 0 return 1 if n = 1 return 2 else if n is even return Alg2 (n/2) * Alg2 (n/2) else return 2 * Alg2 ((n-1)/2) * Alg2 ((n-1)/2) a) Draw a diagram that illustrates the sequence of calls to both algorithms for n=8. b) How many calls are required for each algorithm above for n=8? (i.e. how many nodes in the call tree) c) Since each call takes O(1) in both algorithms above, based on your answer to b) which algorithm do you believe will be faster? d) Write a recurrence relation for each algorithm. Problem 5: Recursion (10 points) Here are two algorithms to compute 2" for any integer n >= 0. Algi (n) Alg2 (n) if n = 0 return 1 else return 2 * Algi (n-1) if n == 0 return 1 if n = 1 return 2 else if n is even return Alg2 (n/2) * Alg2 (n/2) else return 2 * Alg2 ((n-1)/2) * Alg2 ((n-1)/2) a) Draw a diagram that illustrates the sequence of calls to both algorithms for n=8. b) How many calls are required for each algorithm above for n=8? (i.e. how many nodes in the call tree) c) Since each call takes O(1) in both algorithms above, based on your answer to b) which algorithm do you believe will be faster? d) Write a recurrence relation for each algorithm