1

Below code checks if the sum of any pairs of numbers on an array equals to zero. I'm trying to workout the complexity by considering how many times major operations such as variable declarations, value assignments, comparisons, increments, array accesses etc. Normally the complexity would be O(N^2) but I'm very confused when I have to consider the operations specified above. How should I approach this?

int count = 0;
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++)
if(a[i] + a[j] == 0)
count++;
Improve this question
3
  • Do you need big O complexity or exact complexity? Commented Apr 17, 2015 at 19:49
  • I have the big O complexity it's O(N^2). Commented Apr 17, 2015 at 19:50
  • If you sort both arrays (O(N log N)), you will be able to check the sums in O(N) time. Commented Apr 17, 2015 at 19:57

1 Answer 1

Reset to default
2

I'm going to indent the code and highlight each operation explicitly:

int count = 0; // <-- 1 operation

for(int i=0; i<N; i++) // <-- 2 operations per iteration
    for(int j=i+1; j<N; j++) // <-- 2 operations per iteration
        if(a[i] + a[j] == 0) // <-- 4 operations
            count++; // <-- impossible to tell without knowing a. Counting as 1 operation

Here is how you would compute the total number of operations:

enter image description here

That expression simplifies to:

enter image description here

Which is your answer. Note that this is O(N^2), which is consistent with your earlier observation.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments