Run-Time decider

help
1

here are two very similar O(n^2) codes but the difference between there run time is pretty high.
Can someone please tell me what’s the reason for this difference:-

CODE-1(higher run time):-

n=int(input())
s=sorted(list(map(int,input().split())))

dp=[[0 for j in range(2005)] for i in range(2005)]

for d in range(1,n):
    for l in range(n-d):
        r=l+d
        dp[l][r]=min(dp[l+1][r],dp[l][r-1]) + s[r]-s[l]
print(dp[0][n-1])

CODE-2(faster):-

n=int(input())
s=list(map(int,input().split()))
s.sort()

 dp = [[0]*(n) for j in range(n)]

 for l in range(n-2,-1,-1):
   for r in range(l+1,n):
      dp[l][r]=s[r]-s[l] + min(dp[l+1][r],dp[l][r-1])
 print(dp[0][n-1])
2

I think second link probably gives a reason. There’s not much difference due to different initialization method.

2 Likes