Consider the following pseudocode Fa b if b 1 return a else

Consider the following pseudocode:
F(a, b):
if b == 1
return a
else
c = a*a
ans = F(c, b/2)
if b is odd
return a*ans
else
return ans
end
You can assume the following:
• a and b are always positive numbers
• b is always evenly divided by 2
• All arithmetic and logical operations can be completed in constant time
What is the asymptotic running time of the algorithm as a function of b?

Solution

From the question we know that

So let us denote the function complexity as:
f(b) = p + f(b/2)
      = p + (1 + f(b/4)) = 2p +f(b/4)
      = 2p + (1 + f(b/8)) = 3p + f(b/8)
      ...
      = kp + f(b/ 2^k)

the code stops once b/2^k become 1,
or we can represent b = 2^k
therefore we can say k = log₂(b)

thus we can say
      f(b) = p*log₂(b) + f(1)
           = p * log₂(b) + 1   
to represent in Asymptotic big-O notation we remove all constants and we get
     f(b) = O(log(b))

Therefore we can say that f(n) = O(log n)