1
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$

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.