2. Recursion and Iteration (20 points) Consider the function f(x) = x, where x > 0 is a real number and n 20 is a non-negative integer. A recursive definition of f(x)is given below: ifn=0; ifn > l and n is odd; if n > 1 and n is even. f(x) = x" = xm21xxlm/21xx (a) (8 points) Consider the following recursive implementation developed by Prof. Koh: Rec Power(x, n) if (n0) if (n" !) if (n mod 21) return 1.0 return x n is odd return Rec Pover(x, n/2) * Rec Power (x, n/2) *x; /* integer division/ else /* n is even return Rec Pover(x, n/2) Rec Power (, n/2); /* integer division/ (1) (4 points) Draw the computation tree that shows the recursive calls when we call Rec Power (3.0 10), i.e., x = 3.0 and n = 10. (ii (4 points) What is the time complexity of Prof. Koh's recursive implementation in terms of n? What is the space complexity of Prof. Koh's recursive implementation in terms of n? (b) (4 points) You believe that Prof. Koh's recursive implementation is inefficient and that you can have a recursive implementation that has a time complexity of O(log n). Write down your O(logn) recursive implementation Fast Rec Power below Fast.Rec Power (x, n) if (n 0) if (n 1) /* complete your implementation in the space below/ return 1.0 return x (c) (8 points) Consider the following iterative implementation: Itr Power(x, n) pdt 1.0; tmp x; while (n > 0) if (n mod 21) /* n is odd pdt pdt tmp; mptmp tmp n n/2; /* integer division/ return pdt; (i) (4 points) In the following table, write down the values of pdt, tmp, and n as they are updated in the while-loop when we call Itr Pover (3.0, 10). You may write down the values of pdt and tmp in the form of 3, where i is an integer. You may not have to use all entries in the table. pdt 1.0 tmp 3.0 (ii (4 points) What is the time complexity of this iterative implementation in terms of n? What is the space complexity of this iterative implementation in terms of n