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
1 answer

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]
throughA[n1]
to provide an exact number.What you can say is that, at most (with no duplicates in
A[]
), the entire code snippet will runn
^{2} times. Consequently, the rest of this assumes no duplicates: Comparing
i
andj
This comparison will occur
n
^{2} times (again, assuming no duplicates tobreak
the loops). Accessing array element 2 times
 Comparing
AND
operator  Comparing
A[i]
andA[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, wheni
andj
are the same) the rest of theif
condition is ignored. TheAND
is never processed, the array elements are not accessed, and the array elements are not compared.Therefore, these will run
n
^{2}n
times. Then
is because eachj
loop will always match thei
iterator for exactly one value, short circuiting the rest of theif
condition.I'm going to just assume a Clike 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; } }
 Comparing