Concise Recursive Python with Clear Explanation O(log(n)) Binary Search


  • 0
    Z

    Time Complexity: T(n) = T(n/2) + 1 which is in O(log(n)).
    Explanation: x^n = (x^2)^(n/2) = (x * x) ^ (n/2) if n is even. If n is odd, just take one x out of x^n first.

    class Solution(object):
        def myPow(self, x, n):
            if n >= 0:
                return self.helper(x, n)
            else:
                return 1 / self.helper(x, -n)
            
        def helper(self, x, n):
            if n == 0:
                return 1
            else:
                if n % 2 == 0:
                    return self.myPow(x * x, n/2)
                else:
                    return x * self.myPow(x * x, (n-1)/2)
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.