Can calculating Exponentiation, that is, computing x^n , can be done in o(n) time?If so, how would I show this?
Asked
Active
Viewed 352 times
-2
-
x^n is x * x * x * ... * x. Each increment of `n` causes a **single** additional operation => O(n) operations needed to calculate x^n. – Wai Ha Lee May 14 '15 at 10:21
-
1possible duplicate of [I am looking for an algorithm that calculates the power of a number. (x^y), x and y are integers . It must be of complexity O(log\[n\]))](http://stackoverflow.com/questions/7988083/i-am-looking-for-an-algorithm-that-calculates-the-power-of-a-number-xy-x-an) – Paul Hankin May 14 '15 at 10:23
-
@WaiHaLee If you do it by repeated multiplication by x then it's Theta(n), but it can be done in O(log(n)) multiplications. – Paul Hankin May 14 '15 at 10:25
-
@Anonymous - a good point. I was trying to answer the original question (can x^n be calculated in O(n) time?) => it can, but should have mentioned exponentiation by squaring, like amit does in the [answer below](http://stackoverflow.com/a/30234956/1364007). – Wai Ha Lee May 14 '15 at 10:34
-
@WaiHaLee I explained it can be done in `o(n)` multiplications, but CANNOT be done in `o(n)` time. – amit May 14 '15 at 10:38
-
@amit - whoops, you are quite right. In my haste to reply I wrote "time" when I meant "multiplications". – Wai Ha Lee May 14 '15 at 11:10
1 Answers
1
Yes and no.
On one hand, using exponent by squaring, which uses the fact that x^n = (x^(n/2))^2, so by repeatidly squaring the number, you can effectively cut down number of multiplications to O(logN). So, if we assume bounded integer size- it is possible to do it in o(N).
However, since k^n requires log_2(k^n) = n*log_2(k) bits to represent - you cannot do it in o(n), assuming unbounded integers - since the number of bits you need to calculate is itself, Omega(n).
amit
- 175,853
- 27
- 231
- 333