# 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

## Answers:

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[0]`

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;
}
}
```