Runtime of two nested for loops-CodePudding

I am calculating the run time complexity of the below Python code as n^2 but it seems that it is incorrect. The correct answer shown is n(n-1)/2. Can anyone help help me in understanding why the inner loop is not running n*n times but rather n(n-1)/2?

for i in range(n):
    for j in range(i):
        val  = 1

CodePudding user response：

On the first run of the inner loop, when i = 0, the for loop does not execute at all. (There are zero elements to iterate over in range(0)).

On the second run of the inner loop, when i = 1, the for loop executes for one iteration. (There is one element to iterate over in range(1)).

Then, there are two elements in the third run, three in the fourth, following this pattern, up until i = n - 1.

The total number of iterations is 0 1 ... (n - 1). This summation has a well known form*: for any natural m, 0 1 ... m = m * (m 1) / 2. In this case, we have m = n - 1, so there are n * (n - 1) / 2 iterations in total.

You're right that the asymptotic time complexity of this algorithm is O(n^2). However, given that you've said that the "correct answer" is n * (n - 1) / 2, the question most likely asked for the exact number of iterations (rather than an asymptotic bound).

_{* See here for a proof of this closed form.}