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

Question

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?

• Yuval Filmus: What is "the summation of $N$"?
• Yuval Filmus: You can express the running time in terms of whichever parameters you like. There are no rules.
• skyw: 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.

Answer 1

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.