Time complexity of dynamic programming

Question

I'm looking at one of the solutions to the programming problem: Partition a Set into Two Subsets of Equal Sum. The programming problem: Given an array arr[], the task is to check if it can be partitioned into two parts such that the sum of elements in both parts is the same.

The solution is from the link https://www.geeksforgeeks.org/partition-problem-dp-18/. I was calculating the time complexity of the solution called "[Better Approach 1] Using Top-Down DP (Memoization)", which has the following code:

# Python program to partition a Set 
# into Two Subsets of Equal Sum
# using top down approach
def isSubsetSum(n, arr, sum, memo):
    
    # base cases
    if sum == 0:
        return True
    if n == 0:
        return False

    if memo[n-1][sum] != -1:
        return memo[n-1][sum]

    # If element is greater than sum, then ignore it
    if arr[n-1] > sum:
        return isSubsetSum(n-1, arr, sum, memo)

    # Check if sum can be obtained by any of the following
    # (a) including the current element
    # (b) excluding the current element
    memo[n-1][sum] = isSubsetSum(n-1, arr, sum, memo) or\
                     isSubsetSum(n-1, arr, sum - arr[n-1], memo)
    return memo[n-1][sum]

def equalPartition(arr):
    
    # Calculate sum of the elements in array
    arrSum = sum(arr)

    # If sum is odd, there cannot be two 
    # subsets with equal sum
    if arrSum % 2 != 0:
        return False

    memo = [[-1 for _ in range(arrSum+1)] for _ in range(len(arr))]
    
    # Find if there is subset with sum equal 
    # to half of total sum
    return isSubsetSum(len(arr), arr, arrSum // 2, memo)

if __name__ == "__main__":
    arr = [1, 5, 11, 5]
    if equalPartition(arr):
        print("True")
    else:
        print("False")

The website says the time complexity of the above code is O(n * sum), but I thought that it has to be O(2 ^ n) because of the line

    memo[n-1][sum] = isSubsetSum(n-1, arr, sum, memo) or\
                     isSubsetSum(n-1, arr, sum - arr[n-1], memo)

Why is the time complexity O(n * sum) instead of O(2 ^ n)? I'm quite new to calculating the time complexity from a programming code.

This algorithm seems to assume that the input array does not include negative numbers. For instance, for input [1, -5, 4] it returns the wrong result. But this condition is nowhere stated. — trincot
– trincot, Commented May 21 at 17:58

trincot · Accepted Answer · 2025-05-21 19:02:16Z

First of all, the algorithm assumes that the input array consists of unsigned integers. I have not found this constraint in the original post, nor in the referenced third-party site. (Check how it can fail when the input has negative values, like in [1, -5, 4]).

As to the main question:

The worst case complexity is as you have cited: O(𝑛 * 𝑠𝑢𝑚), where 𝑠𝑢𝑚 is the sum of all the values in the input array, i.e. arrSum in the program. It would have been O(2^𝑛) if the algorithm would not have used memoization. But memoization prunes the search tree to a significant extent.

The key insight is that a single call of isSubsetSum will either return in constant time, or will replace a single -1 in the memoization matrix with a Boolean value deferring more work to other calls of this function. The only exception to this rule is where the program checks arr[n-1] > sum:

This special case could have been avoided, by just allowing the program to execute the generic (recursive) flow even in this state, and then test at the top of the function whether sum < 0 and return False in that case, which effectively aborts the second recursive call that is made in the generic flow.

Here is the version that does not have this special case, but deals with it one level deeper in recursion as a base case:

def isSubsetSum(n, arr, sum, memo):
    # base cases
    if sum == 0:
        return True
    if n == 0 or sum < 0:  # added another base case
        return False
    if memo[n-1][sum] != -1:
        return memo[n-1][sum]
    # generic, recursive case:
    memo[n-1][sum] = isSubsetSum(n-1, arr, sum, memo) or\
                     isSubsetSum(n-1, arr, sum - arr[n-1], memo)
    return memo[n-1][sum]

_{Side note: don't use sum as variable name: Python uses this name for a globally available function.}

That way we see that also this apparent exceptional case in the original program is not really one to consider separately. We now truly have two scenarios for a single call of isSubsetSum:

it will return in constant time, or
it will make recursive calls and replace a single -1 in the memoization matrix with a boolean value.

In the second case it is also important to note that the recursive calls never assign a value to the memoization cell that the one making the recursive calls intends to update itself. This is so because the n parameter will get a lesser value with each recursive call.

The above classification is true also for every recursive call that is made. As the matrix has a size of n * (arrSum+1), there are only that many replacements of -1 possible, so the second scenario can only happen that many times. All the other recursive calls thus have a constant execution time.

The second scenario represents an internal node of the recursion tree, while the first scenario represents a leaf node of that same tree. As the recursion tree is a full binary tree, the number of leaves is exactly one more than the number of internal nodes. So in the worst case the number of nodes in the recursion tree is twice the size of the memoization matrix, plus 1.

We can thus conclude that the total number of calls that are made of isSubsetSum -- which is the number of nodes in the recursion tree -- is linear in terms of the memoziation matrix size. The initialisation code in equalPartition also has that complexity as it allocates and assigns the -1 values to that matrix. Therefore the time complexity is O(𝑛 * 𝑠𝑢𝑚)

Collectives™ on Stack Overflow

Time complexity of dynamic programming

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related