# asymptotics – Time complexity of pairs in array double loop

It’s well known task “Checking for Duplicates” and you can found it for example in Tim Roughgarden – Algorithms Illuminated_ Part 1_ The Basics-(2017) 42 page. Let me say, that as here so in book taking last index “i” as $$n=$$“array.length()” have no sense, because then index “j” runs out of borders. But this do not affect our counting.

As always main is to choose operation for count – here its “count = count + 1”. Obviously best case, i.e. least amount of operations, is $$0$$. And worse case, i.e. maximal amount of operations, is sum (I correct it accordingly taking index “i” up $$n-1$$) brought by you $$T(n)=1+2+cdots+(n-1)=frac{n(n-1)}{2}$$ (we consider case $$ngeqslant 2$$).

Now, because $$frac{n(n-1)}{2} leqslant frac{ncdot 2n}{2}=n^2$$, it’s easy to conclude, that worse case $$T(n) in O(n^2)$$.