What is the time complexity for the DP version?


  • 0
    I

    I think it is O(n^5). Let me explain:

    there are n^2 subproblems, since each subproblem is defined by a start and end index (at least how i did it.
    Now for each subproblem, u have to loop from the start to the end index, and then evaluate everything to the left of the operator, and to the right of the operator. so for example if you have "23+57", and you are at the "+", you get all the ways to evaluate 23, and all the ways to evaluate 57, then you go through all the pairings of those and evaluate, so this takes n^2 work,
    so therefore each subproblem takes n^3 non recursive work to do, and there are n^2 subproblems, so the total time complexity is O(n^5). Is this correct analysis? My code is below btw.

    class Solution(object):
        def calculate_util(self, left_op, right_op, operand):
            if operand == '+':
                return left_op + right_op
            if operand == '-':
                return left_op - right_op
            return left_op * right_op
        
        def evaluate_util(self, start, end, exp, cache):
            if (start,end) in cache:
                return cache[(start,end)]
            
            cache[(start,end)] = []
            op_found = False
            for i in xrange(start, end+1):
                if exp[i] in ['+','-','*']:
                    op_found = True
                    left_results = self.evaluate_util(start, i-1, exp, cache)
                    right_results = self.evaluate_util(i+1, end, exp, cache)
                    for left_result in left_results:
                        for right_result in right_results:
                            calculation = self.calculate_util(left_result, right_result, exp[i])
                            cache[(start,end)].append(calculation)
                          
            if not op_found:
                cache[(start,end)] = [int(exp[start:end+1])]
            return cache[(start,end)]
        
        def diffWaysToCompute(self, input):
            """
            :type input: str
            :rtype: List[int]
            """
            cache = {}
            return self.evaluate_util(0, len(input) - 1, input, cache)

Log in to reply
 

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