Time-complexity of nested loop, with varying size

Question

I am trying to understand the time complexity of this algorithm, anyone who can let me know of the runtime complexity descriptively not asymptotically, the code;

array = [-3, 0, 1, 2, -1, 1, -2]
def triplets_sum(nums):
    n = len(nums)
    lst = []
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if nums[i] + nums[j] + nums[k] == 0 and sorted([nums[i], nums[j], nums[k]]) not in lst:
                    lst.append(sorted([nums[i], nums[j], nums[k]]))
    return lst
      
triplets_sum(array)

Answer 1

O(n^3)

Each i would be run n*(n+1)/2 times which gives Triangular numbers. Well, to be more exact, it would be run (n-2)*(n-1)/2, but that's the same O notation.

If you start with n=3, you get 1 run. Every time n goes up, you get what you had before, plus (n-2).

But, of course what you need is the sum of all these, that's called triangular pyramidal and it's n*(n+1)*(n+2)/6 which is O(n^3).

Sorry my last answer incorrectly didn't sum over i and so under counted.

Update with additional explanation

A good place to start is with small n cases. For example, at n = 3, the loop runs once, since i is 1~3, j is 2~3 and k is only 3.
When we move to n = 4, then j is 2~4 and k is 3~4. On the j = 2 run, k runs twice, and on the j = 3 run, k runs only once. That's 3 runs total.
Of course, we can't keep running through all the possibility like this, so I made an excel sheet. For any given n, what i, j, and k values occur.

First, start with an n. They are in green. For any n, what i values are possible? They are listed under i so that any i that's right of an n will happen. For example, at n = 7, the possible values for i are [7, 6, 5, 4, 3]. Ok, so now we know which i values will happen, next what j values will happen for any given i? I decided to be verbose here. For every i, I listed all the possible j values next to it. Let's say we're looking at n = 7 still. One possible i value in that case is 5. When i = 5, then we can see the possible j values are [4, 3, 2]. Ok, getting close now. For each of those j values, how many times will k run? Well, k will always run one fewer time than j, so in the k column, this is the value I wrote.

With all this is written out, now it's time to work backwards and summing up as we go. Let's zero in on n = 7, i = 5, j = 3, k = 1 or 2, I marked that cell in blue. There are 2 possible values for k at this j value. For this i = 5 value, there are 3 possible j values, namely 4, 3, and 2. Summing up the times k runs for each of these, we get 3 + 2 + 1 = 6 which we see in the i total column. The last step is to sum up all the i values that happen for any given n. If n = 7, then we have to sum up all the i values in [7, 6, 5, 4, 3] which is 15 + 10 + 6 + 3 + 1 or 35.

The final step is finding a general solution. We can see that to find i total we are summing up all integers from 1 to (i-2). Then to find the n total we are summing up the i totals. Well, summing up all integers from 1 to x gives Triangular numbers, as I mentioned before, and summing up Triangular numbers gives Triangular pyramidal numbers. The formula for that is n*(n+1)*(n+2)/6. In this case, we start from n = 3 so this particular case would be (n-2)*(n-1)*(n)/6. Plugging in some n values to this matches our hand-derived values. With O notation, we can basically strip out constants, so it would be n * n * n or O(n^3).

This is basically representing a 4D array in excel, so I understand it's not clear at first glance, but if you step through, I think you'll find each step stands. I'm open to corrections or better explanations.

Answer 2

With three nested loops that grow longer in proportion to N, it cannot possibly be anything less than O(N**3). Consider this demonstration.

def countem(n):
    cnt = 0
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                cnt += 1
    return cnt

for z in range(20,120):
    i = countem(z)
    print(z,i,i/(z*z*z))

Here is the output:

20 1140 0.1425
21 1330 0.1436130007558579
22 1540 0.1446280991735537
23 1771 0.14555765595463138
24 2024 0.14641203703703703
25 2300 0.1472
26 2600 0.14792899408284024
27 2925 0.14860539551897575
28 3276 0.14923469387755103
29 3654 0.14982164090368608
30 4060 0.15037037037037038
31 4495 0.15088449531737774
32 4960 0.1513671875
33 5456 0.15182124273033365
34 5984 0.1522491349480969
35 6545 0.1526530612244898
36 7140 0.15303497942386832
37 7770 0.15339663988312638
38 8436 0.15373961218836565
39 9139 0.15406530791146175
40 9880 0.154375
41 10660 0.15466983938132065
42 11480 0.15495086923658352
43 12341 0.1552190373174689
44 13244 0.15547520661157024
45 14190 0.1557201646090535
46 15180 0.15595463137996218
47 16215 0.1561792666364871
48 17296 0.15639467592592593
49 18424 0.15660141607663475
50 19600 0.1568
51 20825 0.1569909009355376
52 22100 0.15717455621301776
53 23426 0.15735137059451762
54 24804 0.15752171925011432
55 26235 0.15768595041322314
56 27720 0.15784438775510204
57 29260 0.15799733251256798
58 30856 0.1581450653983353
59 32509 0.15828784831944842
60 34220 0.15842592592592591
61 35990 0.15855952700886858
62 37820 0.1586888657648283
63 39711 0.15881414294112706
64 41664 0.158935546875
65 43680 0.15905325443786983
66 45760 0.15916743189470461
67 47905 0.15927823568723545
68 50116 0.15938581314878894
69 52394 0.15949030315759993
70 54740 0.15959183673469388
71 57155 0.15969053759174767
72 59640 0.15978652263374485
73 62196 0.15987990242071684
74 64824 0.15997078159240322
75 67525 0.16005925925925926
76 70300 0.1601454293628809
77 73150 0.1602293810086018
78 76076 0.16031119877273722
79 79079 0.16039096298670086
80 82160 0.16046875
81 85320 0.16054463242391911
82 88560 0.16061867935752527
83 91881 0.16069095659747423
84 95284 0.16076152683295541
85 98770 0.16083044982698963
86 102340 0.16089778258518117
87 105995 0.16096357951292553
88 109736 0.16102789256198347
89 113564 0.1610907713672516
90 117480 0.1611522633744856
91 121485 0.1612124139596667
92 125580 0.16127126654064272
93 129766 0.16132886268162022
94 134044 0.16138524219103667
95 138415 0.1614404432132964
96 142880 0.16149450231481483
97 147440 0.1615474545647784
98 152096 0.1615993336109954
99 156849 0.16165017175118185
100 161700 0.1617
101 166650 0.16174884815214194
102 171700 0.16179674484172754
103 176851 0.16184371759826563
104 182104 0.16188979289940827
105 187460 0.1619349962207105
106 192920 0.16197935208259168
107 198485 0.16202288409468077
108 204156 0.16206561499771377
109 209934 0.16210756670313947
110 215820 0.1621487603305785
111 221815 0.1621892162432703
112 227920 0.16222895408163265
113 234136 0.16226799279505053
114 240464 0.16230635067200164
115 246905 0.16234404536862004
116 253460 0.16238109393579073
117 260130 0.16241751284486328
118 266916 0.1624533180120655
119 273819 0.16248852482169338

So, the ratio of loop count to N**3 is converging on a constant.

The question then becomes, what's the big-O value for the processing inside the loop? That, unfortunately, is data dependent. The not in lst is O(N), but that's only going to be done when the sum of the three values is 0. You could change this to O(1) by making that a set instead of a list.

So, perhaps the best we can do is to say "it is at least O(N**3)". If you changed it to use a set instead of a list, it would be simply O(N**3).