Prove that its time efficiency is in theta(nW), its space efficiency is in theta(nW)...

e) For the bottom-up dynamic programming algorithm, prove that its time efficiency is in (nW), its space efficiency is in O(nW) and the time needed to find the composition of an optimal subset from a filled dynamic programming table is in O(n). 2 #function to read weights, values from file 3 def readFile(filename, wt, val): #read words from the file using Loops as follows #open the file using open() with open(filename, 'r') as infile: #read Lines from the file for line in infile: i = 1 #take words from the line for word in line.split(): #first word is weight in that Line if i == 1: #first convert string in int then insert wt.append(int(word,10)) i = i+1 else: #second word is value in that line val.append(int(word,10)) 19 20 22 #bottom-up dynamic programming algorithm 23 def knapsackDP (wt, val, W): #Length of array n = len(wt) 24 #2d array to store bottom up calculations dp = [[O for i in range (W+1)] for i in range(n+1)] #fill array using dynamic programming for i in range(n+1): for w in range (W+1): #first row or column if i==0 or w==0: dp[i][w] = 0 #if next item weight is more than current allowed wt #then dont consider it elif wt[i-1] > W: dp[i][w] = dp[i-1][w] #else check for 2 cases: #1st - consider this item and #2nd- dont consider this item #and take maximum of both cases else: dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]) #return the result of maximum value from Last row, column of arrayt return dp[n][W] 53 def main(): #create List for weight and value wt = [] val = [] #total weight allowed W = 6 #filename fileName = "data.txt" #call function to read from file readFile(fileName, wt, val) #call function for dynamic programming result = knapsackDP (wt, val, w) #print result print("Given weights", wt) print("Given Values",val) print("Given total weight",W) print("Maximum value can be: ",result) 76 77 if _name__ == "__main__": 78 main() 79