Find Power of number in Log(n) Time complexity
# Naive way Time complexity is O(n)
def power(x,n):
if(n==0):
return 1
elif(n%2==0):
return (power(x,n//2)*power(x,n//2))
else:
return (x*(power(x,n//2))*(power(x,n//2)))
# Effective approach Time complexity is O(Log(n))
def powerlog(x,n):
if(n==0):
return 1
temp=powerlog(x,n//2)
if(n%2==0):
return (temp*temp)
else:
return (x*temp*temp)
print(power(2,4))
print(powerlog(4,4))
0 Comments