# Explain the complexity of this algorithm?

Studying the book "Algorithms. Theory and practical application" sort of Stevens. There is an 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 Ledger indicates that the complexity of this algorithm is O(n^2). As the complexity of the outer loop O(n). But if you add up all the internal iteration 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 need you to explain this here is a mathematical transformation of the inner loop. Since I have no idea why this is so. N + (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2 = (N^2 - N) / 2
June 27th 19 at 15:36
June 27th 19 at 15:38
Solution
I think the extra N in the beginning, the inner loop will work (N-1)+(N-2)+...+1 times. And in fact, you compare 2 numbers and if we turn to combinatorics, the first we can take N options, and the second (N-1). Since we order is not important, then divide in half - it turns out N*(N-1)/2
June 27th 19 at 15:40
Solution
If you have to enter the array {a, b, c} then we iterate over combinations of ab ac bc.
Check whether converges with the formula:
(3^2 - 3) / 2 = 3

If the input is {a, b, c, d} then iterate over combinations ab ac ad bc bd cd
Check whether converges with the formula:
(4^2 - 4) / 2 = 6

You can go on and on, and also come together. In General, combinations are considered as: (in our case k = 2).

The attentive reader might notice that 3^2 = 9 and 9 ! = 4 but in evaluating the complexity constant factors are often omitted and instead of the O(2N^2) instead of O(N^2 / 2) write O(N^2), as differences in complexity are not as important as differences on the order of O(N^2) and O(N^3) or O(N!).

Or your question about disclosure of brackets?
Thank you for Your very detailed response. You answered what you need - Rodrick_Bergstrom59 commented on June 27th 19 at 15:43
June 27th 19 at 15:42
Solution
for children:
this is a famous story about Gauss, it sucks described here and here and well described in any textbook XS: Gauss noticed that among the N numbers sum of first and last is equal to the sum of the second and penultimate, equal to the sum of N and N[N-2], etc.
i.e., N+N[n] = N+N[n-1] = N+N[n-2], etc., all such "pairs" - N/2 , then the sum equals (N+N[n]) * N/2 which is equivalent to (N+1)*N/2
the unit is neglected, the resulting quadratic complexity

but for adults: this is a typical entry of the series, for the trained eye, everything is obvious

Find more questions by tags Algorithms