15

Why is time complexity O(1) of pow(x,y) while it is O(n) for x ** y?

Check comment from agf here

Kumar Tanmay
  • 153
  • 1
  • 1
  • 8
  • You’re right – that doesn’t sound accurate. (It originates from a comment by unseen_rider.) – Ry- Feb 17 '18 at 09:26
  • Wish I could comment and ask both of them there :-) – Kumar Tanmay Feb 17 '18 at 09:33
  • 6
    That comment is nonsense. For an integer `n`, both `pow(n, 0.5)` and `n ** 0.5` will simply end up calling the underlying C library's `pow`. (Personally, I'd go with `sqrt` every time: it's much more likely to be correctly rounded and unlikely to be noticeably slower than `pow` or `**`) – Mark Dickinson Feb 17 '18 at 09:36
  • According to [this answer](https://stackoverflow.com/questions/20969773/exponentials-in-python-x-y-vs-math-powx-y), `**`is faster for `float` values, whereas `pow`is faster for `int` values due to the optional modulus argument to the builtin pow. – RunOrVeith Feb 17 '18 at 09:38
  • @RunOrVeith: `pow(x, y)` is faster for `int` values only when you want to do `float` exponentiation anyway, but they still have the same time complexity. – Ry- Feb 17 '18 at 09:51
  • According to [Modular Exponentiation] (https://en.wikipedia.org/wiki/Modular_exponentiation), the memory efficient method is to calculate the modulus on the go instead of leaving it till the exponential is calculated. However, I couldn't understand how it is memory efficient when the modulus is 1? – Kumar Tanmay Feb 18 '18 at 03:07
  • 2
    @KumarTanmay When the modulus is 1, the result will always be 0. So first calculating a big number and then returning 0 at the end would mean you'd have to store that big number in memory until the end. If you mod with 0 along the way, you'll never get to that big number and you'll only store 0 in memory. – sepp2k Feb 18 '18 at 15:02

1 Answers1

35

The statement is wrong.

  • pow is more or less identical to **.
  • pow and ** do integer exponentiation if their arguments are integers. (Python 3 has automatic bignum support, so, for example, a ** b always gives the exact integral result, even if a or b are very large.) This takes O(log(b)) multiplications with exponentiation by squaring, but bignum multiplication isn't constant time, so the time complexity depends on details of the multiplication algorithm used. (Also, Python doesn't quite use exponentiation by squaring, but what Python does use still takes O(log(b)) multiplications.)
  • math.pow, on the other hand, is different. It always does floating point exponentiation and is always O(1). That O(1) complexity isn't because it's any more efficient than pow or **; it's because floating point sacrifices accuracy and range. For cases where the non-constant complexity of integer exponentiation actually matters, math.pow will give much less precise results or throw an OverflowError.

Further details (from reviewing other questions on Stack Overflow, and from poking a bit at the Python source):

  • pow (see here) and ** (see here) both call the same PyNumber_Power function. In practice, ** can be faster, because it avoids the overhead of an extra symbol lookup and function call.
  • The integer implementation of pow / ** can be seen here.
  • math.pow, on the other hand, always calls the C library's pow function, which always does floating point math. (See here and here.) This is often faster, but it's not precise. See here for one way that pow might be implemented.
  • For floating point numbers, pow / ** also call the C library's pow function, so there's no difference. See here and here.

You can paste these commands into your IPython session if you want to play with this yourself:

import timeit

def show_timeit(command, setup):
    print(setup + '; ' + command + ':')
    print(timeit.timeit(command, setup))
    print()

# Comparing small integers
show_timeit('a ** b', 'a = 3; b = 4')
show_timeit('pow(a, b)', 'a = 3; b = 4')
show_timeit('math.pow(a, b)', 'import math; a = 3; b = 4')

# Compare large integers to demonstrate non-constant complexity
show_timeit('a ** b', 'a = 3; b = 400')
show_timeit('pow(a, b)', 'a = 3; b = 400')
show_timeit('math.pow(a, b)', 'import math; a = 3; b = 400')

# Compare floating point to demonstrate O(1) throughout
show_timeit('a ** b', 'a = 3.; b = 400.')
show_timeit('pow(a, b)', 'a = 3.; b = 400.')
show_timeit('math.pow(a, b)', 'import math; a = 3.; b = 400.')
user2357112
  • 260,549
  • 28
  • 431
  • 505
Josh Kelley
  • 56,064
  • 19
  • 146
  • 246