1
$\begingroup$

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
Improve this question
$\endgroup$
9
  • $\begingroup$ I mean recursive calls $\endgroup$
    – Parviz Pirizade
    Sep 20, 2021 at 18:43
  • $\begingroup$ My bad. I'm used to different notation, so I thought you meant the recursion depth is $1$. $\endgroup$
    – nir shahar
    Sep 20, 2021 at 18:43
  • 1
    $\begingroup$ What is $n$ in your question? is it the size of $b$ in bits? $\endgroup$
    – nir shahar
    Sep 20, 2021 at 18:47
  • $\begingroup$ it means linear time. $\endgroup$
    – Parviz Pirizade
    Sep 20, 2021 at 18:48
  • 2
    $\begingroup$ 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 $\endgroup$
    – nir shahar
    Sep 20, 2021 at 18:52

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.