Explain the complexity of this algorithm?

Question

Algorithms

I am studying the book "Algorithms. Theory and practical application" by Rod Stevens. There are algorithms for finding duplicates.

boolean containsDuplicate(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] == array[i]) {
                return true;
            }
        }
    }
    return false;
}

The book states that the complexity of this algorithm is O(n^2). Since the complexity of the outer loop is O(n). And if we add up all the iterations of the inner N + (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2 = (N^2 - N) / 2, which means, that the complexity is O(n^2).
Actually, I only ask you to explain this mathematical transformation of the inner loop. Because I really don't understand why this happens. N + (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2 = (N^2 - N) / 2

Answer 1

It seems to me that the extra N at the beginning - the inner loop will run (N-1)+(N-2)+...+1 times. But in fact, you are comparing 2 numbers and if you turn to combinatorics, then you can take the first N options, and the second (N-1). Since the order is not important to us, we divide in half - this is N * (N-1) / 2