What is the computational complexity of the function pow in Python?

hirof 0
Viewed 49

I want to know the computational complexity of pow in Python. To two-arg (plain exponentiation).

I have this code, and I know the computational complexity of a for is O(n), but I don't know if the pow affect the complexity.

def function(alpha,beta,p):
    for x in range(1,p):
      beta2 = (pow(alpha, x)) % p 
        if beta == beta2:
            return x
        else:
            print("no existe")
exponentiation complexity-theory algorithm python
1 Answers

As mentioned by comment, the official Python interpreter does a lot of optimization for its internal math functions. The usual pow operation of type A ** B calls two variable Pointers for evaluation (actually all Python variables are a combination of Pointers, making it unnecessary to initialize data types), but this is a slow process. On the contrary, the interpreter can optimize the data in the POW, fix their variable types as int , thus to reduce complexity. You can also read this answer, which should fully explain your question Why is time complexity O(1) for pow(x,y) while it is O(n) for x**y?

Oh now you post a code, that clearify the problem. Usually, in Algorithm we treat the time complexity of OPERATION as O(1), this dosn't matter how many operations you have in a loop, because that is the def of O() notation. And for usual program, only the loop matters, for your progrom the complexity should only be O(n)

def function(alpha,beta,p):
for x in range(1,p): # Only one loop
  beta2 = (pow(alpha, x)) % p 
    if beta == beta2:
        return x
    else:
        print("no existe")
Algorithm_Traveller0
Related