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

  • answered 2018-03-11 14:32 McGuireV10

    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 n2 times. Consequently, the rest of this assumes no duplicates:

    • Comparing i and j

    This comparison will occur n2 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 n2-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;
        }
    }