3) (30 points) Consider the following recursive algorithm for computing 2", for any integer n>0. Algorithm Power(n) if n -1 return 2 else return Power(In/2) Power(In/21) a) What general design technique is this algorithm based on? b) Set up a recurrence (with an appropriate initial condition) for the approximate number of multiplications M(n) made by the algorithm, and solve it for n-2*, a power of two, as a function of n. Show all your work, as well as an example when k-3 c) Give a proof by mathematical induction that this algorithm is correct. Hint: To avoid having to deal with equations for the floor and ceiling functions, take cases on whether n is even or odd