CODEWITHSUNDEEP
algorithmcomplexity-theory
user2713650
user2713650

Reputation: 99

Counting elementary operations

I need to count the elementary operations of the code below:

public static int findmax(int[] a, int x) {
    int currentMax = a[0];

    for (int i = 1; i < a.length; i++) {
        if (a[i] > currentMax) {
        currentMax = a[i];
        }
    }

    return currentMax;
}

I understand that a primitive operation (such as assigning a value to a variable) is given a value of 1. So here assigning a[0] to currentMax accounts for 1 primitive operation executed.

Within the for loop: assigning 1 to i, also accounts for 1. And i < a.length, and i++ are n - 1 each (i.e 2(n-1)). However, I get confused as to how to deal with the if statement. I'm aware that we're looking for the worst case (so we'd need to perform the if condition and the statement nested within that block). But I'm not sure what this is in terms of a primitive operation.

Upvotes: 1

Views: 4620

Answers (1)

Boris Dalstein
Boris Dalstein

Reputation: 7748

Before the loop iterations

int currentMax = a[0];

Assignment: counts for 1.

int i = 1

Assignment: counts for 1

For each of the n iterations of the loop (note that here, n=a.length-1)

i < a.length

Comparison (returns true): counts as 1

i++

Incrementation: counts as 1

a[i] > currentMax

Comparison: counts as 1

currentMax = a[i];

Assignment: counts as 1

When existing the loop

i < a.length

Comparison (return false): counts as 1

CONCLUSION

You have in the worst case 1 + 1 + n*(1+1+1+1) + 1 = 4*n + 3 elementary operations, hence the conplexity of your algorithm is Θ(n).

More specifically, to handle the if statement, you have of course to take into account the computation of its argument, but the word "if" itself doesn't count. The processor just jumps instantly to the next instruction depending on the result. Some may argue that this conditionnal jump may count as 1, but anyway this has no importance, since 4*n + 3 is the same complexity as 5*n + 3, i.e. Θ(n).

If you want to be precise and keep the constants, then you have to specify what does it mean exactly, such as:

  • n+2 assignments
  • n incrementations
  • 2*n+1 comparisons

In which case it is clear what you decided to count as elementary operations or not. But for instance, you could have also decided that accessing the array like a[i] was worth counting (it is actually one pointer addition plus one memory access), so you would add:

  • 2*n+1 array access

Or if you want to be more precise, and separate the fact that one of the access is a[0] and do not perform pointer arithmetic, you would say:

  • 2*n+1 memory access
  • 2*n pointer additions

So you see that it is up to you to decide what do you count as "elementary operations", and all answers are equally true.

Upvotes: 3

Related Questions