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

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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