given the following method to calculate a power

**DO NOT USE THE MASTER THEOREM**

A. Show a trace of the steps that would be followed by this algorithm with an input of a = 2, n = 63. How many times is the method called including the initial call to FastPower(2,63)? In total, how many multiplications have to be performed to compute 2^63 (treat the calculation x * x * 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)? Using big-O notation, what is the worst-case number of multiplications required by FastPower, as a function of the exponent n?

FastPower(a,n): if n = 1 return a x + FastPower(a, In/2]) if n is even return x x else return xx. a FastPower(a,n): if n = 1 return a x + FastPower(a, In/2]) if n is even return x x else return xx. a