1
$\begingroup$

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
$\endgroup$
2
  • 2
    $\begingroup$ Why do you think count = count + 1; should or should not be taken into account? Is it because it's in an if-statement? Or are you just generally wondering what you should be counting? $\endgroup$ Sep 13 '20 at 21:29
  • $\begingroup$ Or are you just generally wondering what you should be counting?, Exactly! $\endgroup$
    – John Smith
    Sep 14 '20 at 3:11
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.