-2
$\begingroup$

This question already has an answer here:

I have algorithm that contains next loops:

for (int i = 0; i < size; ++i) {

    for (int j = i + 1; j < size; ++j) {
        //Do stuff
    }
}

I found that this algorithm has $O(n^2)$ complexity but I can't understand why? I.e. if $N = 4$ then $n^2 = 16$ but my loop has 6 iterations only. Just it's a half of $n^2$ value.

P.S. I understand never how to measure the complexity of the algorithm, I only can understand how to write it in the mathematics.

$\endgroup$

marked as duplicate by Evil, David Richerby, Raphael Sep 7 '16 at 9:31

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ The point is that $n^2/2 = O(n^2)$. $\endgroup$ – Yuval Filmus Sep 7 '16 at 2:17
  • $\begingroup$ Do we just reduce a factor? $\endgroup$ – Шах Sep 7 '16 at 2:47
  • 2
    $\begingroup$ @Шах I suggest you check the definition of big-O. $\endgroup$ – David Richerby Sep 7 '16 at 7:29
1
$\begingroup$

Your "stuff" will get executed $N(N - 1)/2 = 0.5N^2 - 0.5N$ times. When analyzing the asymptotic complexity, only the highest order term is kept, and multiplicative constants are removed, leaving you with $O(N^2)$.

It works this way because we're interested in what happens when $N$ goes to infinity (scalability).

$\endgroup$
  • $\begingroup$ It seems, I understood. Thank you for explanation! $\endgroup$ – Шах Sep 7 '16 at 6:18

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