# Number of Primitive operations in IF Statement

I am new to Design and Analysis of Algorithms. I have a nested loop and and if statement.I am unable to determine the primitive operations being done in if statement. The statements are as follows:

``````for (i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j and A[i]==A[j])
duplicate=true
break;
if(duplicate)
break;
``````

i am determining the No of operations in if statement as follows:

``````Accessing array element 2 Times
comparing i and J
Comparing A[i] and A[j]
Comparing AND Operator
``````

all this is being done N times. Am i right in guessing the number of primitive operations in if statement? if not then please help me correct this. Thanks

Technically, we can't determine how many times this will happen since it depends on the contents of the array. Once a duplicate is found, the whole thing terminates. We'd have to see the complete contents of all of the elements from `A` through `A[n-1]` to provide an exact number.

What you can say is that, at most (with no duplicates in `A[]`), the entire code snippet will run `n``2` times. Consequently, the rest of this assumes no duplicates:

• Comparing `i` and `j`

This comparison will occur `n``2` times (again, assuming no duplicates to `break` the loops).

• Accessing array element 2 times
• Comparing `AND` operator
• Comparing `A[i]` and `A[j]`

These other operations only happen if `i != j` is true, because most modern languages "short circuit". When that first condition fails (in other words, when `i` and `j` are the same) the rest of the `if` condition is ignored. The `AND` is never processed, the array elements are not accessed, and the array elements are not compared.

Therefore, these will run `n``2``-n` times. The `-n` is because each `j` loop will always match the `i` iterator for exactly one value, short circuiting the rest of the `if` condition.

I'm going to just assume a C-like language and correctly format the code as if this were a C# snippet:

``````// n and A[] initialized elsewhere
bool duplicate = false;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i != j && A[i] == A[j])
{
duplicate = true;
break;
}
}
if(duplicate)
{
break;
}
}
``````