# A Nested Loop

suggest changeThe following function checks if an array has any duplicates by taking each element, then iterating over the whole array to see if the element is there

_Bool contains_duplicates(const int *array, size_t len) { for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len; j++) { if (i != j && array[i] == array[j]) { return 1; } } } return 0; }

The inner loop performs at each iteration a number of operations that is constant with `n`

. The outer loop also does a few constant operations, and runs the inner loop `n`

times. The outer loop itself is run `n`

times. So the operations inside the inner loop are run `n^2`

times, the operations in the outer loop are run `n`

times, and the assignment to `i`

is done one time. Thus, the complexity will be something like `an^2 + bn + c`

, and since the highest term is `n^2`

, the O notation is `O(n^2)`

.

As you may have noticed, we can improve the algorithm by avoiding doing the same comparisons multiple times. We can start from `i + 1`

in the inner loop, because all elements before it will already have been checked against all array elements, including the one at index `i + 1`

. This allows us to drop the `i == j`

check.

_Bool faster_contains_duplicates(const int *array, size_t len) { for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { if (array[i] == array[j]) { return 1; } } } return 0; }

Obviously, this second version does less operations and so is more efficient. How does that translate to Big-O notation? Well, now the inner loop body is run `1 + 2 + ... + n - 1 = n(n-1)/2`

times. This is *still* a polynomial of the second degree, and so is still only `O(n^2)`

. We have clearly lowered the complexity, since we roughly divided by 2 the number of operations that we are doing, but we are still in the same complexity *class* as defined by Big-O. In order to lower the complexity to a lower class we would need to divide the number of operations by something that *tends to infinity* with `n`

.