0

I was learning about time complexity recently and I was wondering time complexity of a algorithm to compute a^n. My answer will be O(n). However, I was thinking about the divide and conquer method. As a^n/2 * a^n/2 = a^n. Is it possible to turn time complexity of an algorithm a^n into a algorithm with O(logn) time complexity but I was stuck thinking how would such an algorithm be and how would it works?

I would greatly appreciate if anyone could share their thoughts with me.

LYH
  • 41
  • 4
  • Does this answer your question? [How did this algorithm for computing a^n get rewritten to run in O(log n) time?](https://stackoverflow.com/questions/19218135/how-did-this-algorithm-for-computing-an-get-rewritten-to-run-in-olog-n-time) – derpirscher Feb 08 '22 at 23:26
  • It would work exactly as you wrote. `a^n/2 * a^n/2 = a^n` is a viable approach to defining `a^n` recursively. You only need to take care of the base case, and of the case of odd `n` (not too difficult). – n. m. could be an AI Feb 08 '22 at 23:39
  • Does this answer your question? [The most efficient way to implement an integer based power function pow(int, int)](https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int) – user3386109 Feb 08 '22 at 23:39
  • you can do this is in `O(1), O(log(n)), O(n)` and worse depending on the platform,algorithm, accuracy and `a,n` restrictions (are they int,fixed,floating point are they base size or bignums)? see [Power by squaring for negative exponents](https://stackoverflow.com/a/30962495/2521214) ... you can use LUT,approximations,binary search,power by squating, `log/exp`... – Spektre Feb 09 '22 at 09:21

0 Answers0