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

Question

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

Check comment from agf here

Answer 1

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.')