0

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")
hirof
  • 11
  • 3
  • 1
    Are you asking about two-arg `pow` (plain exponentiation) or three-arg `pow` (modular exponentiation)? The [latter has been covered here before](https://stackoverflow.com/q/5246856/364696). – ShadowRanger Sep 19 '22 at 22:06
  • two-arg, plain exponentiation – hirof Sep 19 '22 at 22:10
  • 1
    To be clear, in the code you posted, you *should* be using three-arg `pow`. `(pow(alpha, x)) % p` gets the same result as `pow(alpha, x, p)`, but it does it *much* more slowly (when `alpha` and `x` are large enough, it can take minutes, hours or even days to do it the former way, while the latter way gets the same result in the blink of an eye). As is, your code will be incredibly slow (assuming `p` is of any size), but at least you have a *chance* of getting your answer with three-arg `pow`, you have basically no chance at all with two-arg `pow` (or the clearer equivalent, `alpha ** x % p`). – ShadowRanger Sep 19 '22 at 22:42

1 Answers1

-1

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_Traveller
  • 1
  • 1