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)) {

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?

  • $\begingroup$ What is "the summation of $N$"? $\endgroup$ May 30 '20 at 12:50
  • $\begingroup$ You can express the running time in terms of whichever parameters you like. There are no rules. $\endgroup$ May 30 '20 at 12:50
  • $\begingroup$ 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. $\endgroup$
    – skyw
    May 30 '20 at 12:53

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.