1:
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n < 0:
return 1.0/self.myPow(x, -n)
elif n==0:
return 1
elif n == 1:
return x
elif n%2 == 1:
return self.myPow(x, n//2) * self.myPow(x, n//2) * x
else:
return self.myPow(x, n//2) * self.myPow(x, n//2)
2:
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n==0:
return 1
elif n==1:
return x
elif n < 0:
return 1 / self.myPow(x, -n)
elif n%2 == 1:
return x * self.myPow(x, n-1)
else:
return self.myPow(x*x, n//2)
I implemented power functions in two different ways.
I was expecting the time complexity to be the same, but when trying on leetcode, 1) timed out and failed for some examples, but 2) succeeded.
Is there a reason why that was the case? I thought time complexity would be the same for both.
The order of if conditions should not affect the complexity in this particular case and has negligible effect on performance. The biggest difference is that there are 2 recursive calls of self.myPow(x, n//2) in both last cases of Solution #1. You should have instead called it once, stored it in a variable, and multiplied them together to avoid redundancy.
# 1
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n < 0:
return 1.0/self.myPow(x, -n)
elif n==0:
return 1
elif n == 1:
return x
elif n%2 == 1:
half_pow = self.myPow(x, n//2)
return half_pow * half_pow * x
else:
half_pow = self.myPow(x, n//2)
return half_pow * half_pow
This reduces the complexity from O(n) to O(log(n)), the same as that of Solution #2