Studying the book "Algorithms. Theory and practical application" sort of Stevens. There is an algorithms for finding duplicates.

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**

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

asked June 27th 19 at 15:36

3 answers

answered on

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

answered on

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?

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

answered on

Solution

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[3] and N[N-2], etc.

i.e., N[1]+N[n] = N[2]+N[n-1] = N[3]+N[n-2], etc., all such "pairs" - N/2 , then the sum equals (N[1]+N[n]) * N/2 which is equivalent to (N+1)*N/2

the unit is neglected, the resulting quadratic complexity

Find more questions by tags Algorithms