# The complexity of the algorithm with loops [duplicate]

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.

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

## 1 Answer

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

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