Is the time complexity of my recursion O(N!^2)? (Python)


  • 0
    S

    My solution is time limit exceeded, but this is probably what would actually happen during a real interview. Is the time complexity O(N!^2)?

    Since T(N) = N * N * T(N-1) = N * N * (N-1) * (N-1) * T(N-2) ~ N! * N! = O(N!^2)

    def maxProfit(self, k, prices):
            """
            :type k: int
            :type prices: List[int]
            :rtype: int
            """
            if len(prices) < 1 or k == 0: return 0
            res = 0
            for i in range(len(prices)-1):
                buy = prices[i]
                for j in range(i+1, len(prices)):
                    if prices[j] > buy:
                        res = max(res, prices[j] - buy + self.maxProfit(k-1, prices[j+1:]))
            return res
    

Log in to reply
 

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