Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 2

Problem:

Consider the following pseudocode for calculating ab (where a and b are positive integers)

      FastPower(a,b) : 

              if b = 1 

                   return a 

              otherwise 

                   c := a*a 

                   ans := FastPower(c,[b/2]) 

               if b is odd 

                   return a*ans 

               otherwise return ans 

end

Here [x] denotes the floor function, that is, the largest integer less than or equal to x.
Now assuming that you use a calculator that supports multiplication and division (i.e., you can do multiplications and divisions in constant time), what would be the overall asymptotic running time of the above algorithm (as a function of b)?

Solution:

Denote the time to run this algorithm $ T(n) $, (we use $ n $ here instead of $ b $ to avoid name clash with the master method variables), so we have:

$ T(n) = T([n/2]) + O(1) $.

Using the master method terminologies, we have

$ a = 1 $, $ b = 2 $, $ d = 0 $.

Notice we have $ 1 = a = b^d = 1 $, therefore, the answer is $ O(\log n) $.