(6 marks) (Based on material by Jeff Erickson] Given a number a and a positive integer n, one way to compute a" is to use the following simple algorithm. The total number of multiplications required is n - 1. SlowPower(a,n): xa for i from 2 ton xx. a return x However, a more efficient algorithm is the following: Fast Power(a,n): if n = 1 return a x + FastPower(a, [n/2]) if n is even return x. x else return x X a (a) Show a trace of the steps that would be followed by the FastPower algorithm for an input of a = 2, n = 63. How many times was FastPower called, including the initial call to FastPower(2,63)? In total, how many multiplications had to be performed to compute 263 (treating the calculation 2.2.a as two multiplications)? (b) As a function of n, write an exact expression for the number of times FastPower gets called when we run FastPower(a,n). (Possibly helpful hint: Find the point at which the number of calls increases from one value to another, by testing a few consecutive values of n like n = 62, n = 63, n = 64, n = 65.) Using big-O notation, what is the worst-case number of multiplications required by FastPower, as a function of the exponent n? Explain. [Reminder: You may not use the Master Theorem in your explanation for this question.]