Consider the following recursive algorithm for computing 2, for any integer n > 0. Algorithm Power(n)...

 

Transcribed Image Text:

Consider the following recursive algorithm for computing 2", for any integer n > 0. Algorithm Power(n) if n = 1 return 2 else return Power([n/2]) * Power[[n/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 = 2k, 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. Consider the following recursive algorithm for computing 2", for any integer n > 0. Algorithm Power(n) if n = 1 return 2 else return Power([n/2]) * Power[[n/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 = 2k, 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.