Number of primetive operations

Question

0.00/5 (No votes)

See more:

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 statement is

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;

What I have tried:

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

Accessing array element 2 Times
comparing i and
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 in advance

Posted 11-Mar-18 3:14am

Jamsdhaid

Updated 11-Mar-18 4:12am

v2

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard MacCutchan · Accepted Answer · 2018-03-11T03:51:00

Solution 1

This is fairly straightforward if we add some more spaces and parentheses:

C++

if ( (i != j) and (A[i] == A[j]) )
         v     v         v
         |     |         +-----> equality operator comparing two array objects
         |     +---------------> AND logical operator testing if both expressions are true
         +---------------------> inequality operator comparing i and j

- first test if i is not equal to j.
- if that is true then the AND operator means we must test the next expression
- test if array element A[i] is equal to A[j]
- If both are true then the whole expression is true

Posted 11-Mar-18 3:51am

Richard MacCutchan

Comments

Jamsdhaid 11-Mar-18 9:53am

@Richard Whether it will not cost for accessing the array elements?
then according to the upper Loops. what can be its complexity? Will you please make it clear? and what if the 1st condition is false?

Richard MacCutchan 11-Mar-18 10:03am

What do you mean by "what can be its complexity"?
There are two loops: the outer one iterates through all the elements of the array. The inner loop does the same, and whenever the two indices are different the code compares the elements. If they are the same then it sets duplicate=true. However, that only tells you that you have one or more duplicates, not exactly how many or where they are.

Jamsdhaid 11-Mar-18 10:09am

Sorry. it's not complexity. But i am trying to ask that whether it will not cost for Accessing the array as A[i] and A[j] where both i and j have different values.
if it will cost for Accessing the array than, what will be its Time Complexity.

[no name] 11-Mar-18 10:24am

Looks like you are asking about short circuit Evaluation, which most Compilers do Support. You can read about it here: Short-circuit evaluation - Wikipedia[^]

In case i and j are the same i!= j becomes false and therefore the AND connected term will not be evaluated because the result is allready complete. So no A[i], A[j] Access in this case.

Jamsdhaid 11-Mar-18 10:31am

What will be the Cost of the if Statement. Would it be n*n ?

Richard MacCutchan 11-Mar-18 10:34am

Yes, but remember there is one case in each iteration of the inner loop where i and j are equal, so it will not evaluate the second expression.

Jamsdhaid 11-Mar-18 10:43am

if it doesn't evaluate the 2nd portion. then what would be its complexity? would it be n^2-n ?
if so, then which one should i use in my analysis?

Richard MacCutchan 11-Mar-18 10:51am

Sorry no idea; that is mathematics not programming.

Jamsdhaid 11-Mar-18 11:01am

okay. thanks for your time

CPallini 11-Mar-18 15:56pm

The complexity is O(n²) independently on 'array access cost', 'boolean expression shortcuts' or whatever.

Jamsdhaid 11-Mar-18 10:32am

or it would be n+n+n? as there are three operations are being done in this statement

Richard MacCutchan 11-Mar-18 10:25am

The outer loop iterates the array once, i.e it selects each element of the array. The inner loop iterates the array once for each iteration of the outer loop. So the time taken by the inner loop is n (elements) times n (outer iterations).