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)$.