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)$.