Consider the following pseudocode for calculating ab, where a and b are positive integers. 19 FastPower...

Transcribed Image Text:

Consider the following pseudocode for calculating ab, where a and b are positive integers. 19 FastPower Input: positive integers a and b. Output: ab. return a if b=1 then else c:=b.b ans:=FastPower(c, [b/2]) if b is odd then else return a ans return ans Assume for this problem that each multiplication and division can be performed in constant time. What is the asymptotic running time of this algorithm, as a function of b? Consider the following pseudocode for calculating ab, where a and b are positive integers. 19 FastPower Input: positive integers a and b. Output: ab. return a if b=1 then else c:=b.b ans:=FastPower(c, [b/2]) if b is odd then else return a ans return ans Assume for this problem that each multiplication and division can be performed in constant time. What is the asymptotic running time of this algorithm, as a function of b?

Answer rating: 100% (QA)

The given pseudocode is implementing the Fast Power algorithm for calculating ab where a and ... View the full answer