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

  • 0

    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)
                return 1 / self.helper(x, -n)
        def helper(self, x, n):
            if n == 0:
                return 1
                if n % 2 == 0:
                    return self.myPow(x * x, n/2)
                    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.