Time complexity of code running at most summation(N) times in a loop

Let’s say I have a JavaScript loop iterating over input of size N. Let’s say all elements in N are unique, so the includes method traverses the entire output array on each loop iteration:

let out = []
for (x in N) }
if (!out.includes(x)) {
out.push(x)
}
}

The worst case runtime of the code inside the loop seems to be not O(N), but the summation of N, which is substantially faster.

Is this properly expressed as O(N^2) overall or is there a standard way to convey the faster asymptotic behavior given the fact that the output array is only of size N at the end of the loop?

• What is "the summation of $N$"? – Yuval Filmus May 30 '20 at 12:50
• You can express the running time in terms of whichever parameters you like. There are no rules. – Yuval Filmus May 30 '20 at 12:50
• What I mean is, if N has 4 elements and all elements are unique, includes method will run over the output array 0+1+2+3 times in total. This is clearly not N times per call, so I can’t see how this algorithm would be N ^ 2 in the size of the input, but would like to describe its worst case complexity somehow. – skyw May 30 '20 at 12:53

1 Answer

If i understand you correctly, then the following holds: $$\sum_{k=1}^nk= \frac{n(n+1)}{2} \ge \frac{n^2}{2} = \Theta (n^2)$$

Thus there is no asymptotic gain.