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

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?
Step by Step Solution
3.43 Rating (153 Votes )
There are 3 Steps involved in it
The given pseudocode is implementing the Fast Power algorithm for calculating ab where a and ... View full answer
Get step-by-step solutions from verified subject matter experts
Document Format (2 attachments)
66430f5b5664e_952657.pdf
180 KBs PDF File
66430f5b5664e_952657.docx
120 KBs Word File
