# Master Method: Divide and Conquer

According to my evaluation ,the overall asymptotic running time of the below algorithm is O(n)  ,since x (number of recursive calls) is 1, and y ( the number of splits) is 2 , and finally z ( the power of amount of work done outside of the recursion call) is 1, hence x<y^{d}, but my answer turned out to be wrong . Why?

 FastPower(a,b) :
if b = 1
return a
else
c := a*a
ans := FastPower(c,[b/2])
if b is odd
return a*ans
else return ans
end

• I mean recursive calls Sep 20, 2021 at 18:43
• My bad. I'm used to different notation, so I thought you meant the recursion depth is $1$. Sep 20, 2021 at 18:43
• What is $n$ in your question? is it the size of $b$ in bits? Sep 20, 2021 at 18:47
• it means linear time. Sep 20, 2021 at 18:48
• I'm asking what $n$ means in this context. What value does it represent? The run-time is dependent on $n$, so we have to first understand what $n$ relates to Sep 20, 2021 at 18:52

FastPower will compute $$a^b$$ using the following recurrence:
$$\begin{equation}a^b=\begin{cases}a & \text{if }b=1\\ (a^2)^{\frac{b}{2}} & \text{if }b\text{ is even}\\ a\cdot(a^2)^{\frac{b-1}{2}} & \text{if }b\text{ is odd}\end{cases}\end{equation}$$
This is $$O(\log{b})$$ since $$b$$ decreases by at least a factor of $$2$$ each recursive call. This assumes multiplication takes constant time since we perform $$O(\log{b})$$ multiplications.