[Python] Time complexity of dynamic programming

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.

Continue reading...