Time complexity of pairs in array double loop

Question

I know, that the following is: O(n^2),

int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

But, should something like count = count + 1; be taken into account? For predicting or making up a complex time equation, or using sum notation,

n + n-1 + n-2 + n-3 + (…) + 1

Answer 1

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 $n\geqslant 2$).

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

Answer 2

The time complexity of an algorithm depends on the model of computation. Algorithms are usually analyzed in the RAM machine, in which basic operations on machine words (such as assignment, arithmetic and comparison) cost $O(1)$. A machine word has length $O(\log n)$, where $n$ is the size of the input.

In your case, the size of the input is at least $n$ (defined to be the length of array), and so count fits in a single machine word. Each of the basic operations in the algorithm cost $O(1)$, and so the overall time complexity is $\Theta(n^2)$, since the algorithm executes this many basic operations.