If n is a positive integer and x is any real number, then x^n corresponds to repeated multiplication of x n
times.
x^n = x * x * x * .... * x
x^n is represented as pow(x, n)
pow(x, n) implementation in Python
Brute-Force Implementation
#!/usr/bin/env python3
# Function to implement power x^y
def power(x, y):
temp = 1
if y>0:
while y>0:
temp *= x
y -= 1
# handle negative y and float x
else:
while y<0:
temp /=x
y += 1
return temp
Time Complexity
Time Complexity: O(n)
Optimised Implementation
x^n is represented as pow(x, n)
#!/usr/bin/env python3
# Function to implement power x^y
def power(x, y):
if(y == 0):
return 1
temp = power(x, int(y/2))
if (y % 2 == 0):
return temp * temp
else:
# handle negative y and float x
if(y > 0):
return x * temp * temp
else:
return (temp * temp)/x
Time Complexity
Time Complexity: O(log(n))