Precise Big O Execution Count

Question

Determine the precise Big-Oh values for the following code sample, based on the number of statement executions.

Keep the following considerations in mind:

• Remember to consider each statement in compound statements separately.
• Pay close attention to the initial and end values of loop variables!
• Loops such as “for” and “while” contain an implicit “jump” instruction that causes execution to proceed from the end of the loop back to the beginning of the loop.

Code sample:

for (int i = 0; i < n; i++){
   for (int j = i; j < n; j++){
      sum += i;
   }
}

The answer above is O(4N^2 + 5N + 2), but I am not entirely sure how the answer is counted. I am trying to better understand how to count the executions.

Answer 1

As noted by Stephen the actual algorithmic complexity is simplified to O(N^2) but since your question was about measuring the amount of executions, i'll try and count them for you.

for (int i = 0; i < n; i++){
   for (int j = i; j < n; j++){
      sum += i;
   }
}

Firstly the outer loop

int i=0 will only be executed once.

i < n will be executed n+1 times

i++ will be executed n times

Therefore we have 2n+2 executions for the outer loop.

Let's clear something first. The outer loop will run n times and the inner loop will run n/2 times (on average). Therefore each instruction in the inner loop will be executed n * n/2 = (n^2)/2 times.

The inner loop

int j = i will be executed n times (remember it's in a loop)

j< n will be executed n+1 * n/2 = (n^2)/2 + n/2 times

j++ will be executed n*(n/2) = n^2/2 times

Now, remember each instruction in the inner loop will run (n^2)/2 times.

sum += i is basically 2 executions that will be executed n^2/2 times each. So this adds another n^2 executions

Adding them in total: (2n + 2) + n + (n^2)/2 + n/2 + (n^2)/2 + n^2 = 2n^2 + (7/2)n + 2

Adding the jump instructions which are n for the outer loop and n^2/2 for the inner loop we get the total of (5/2)n^2 + (9/2)n + 2.

Well either me or your professor has missed something , hopefully this helps a little though since it might give you an idea on how to count the amount of executions. I don't know why that's useful though

Answer 2

The Big O for the complexity of that code is O(N^2). Any other answer is based on a misunderstanding of the mathematical definition of Big O notation and / or the conventions for writing it¹.

You say that "the answer above is O(4N^2 + 5N + 2)". That's incorrect. It may be that the instruction count (according to certain assumptions about instructions and compilers) is 4N^2 + 5N + 2. However, that's NOT the conventional way to write the Big O complexity class for the function.

A complexity class is not a function. It is an infinite set of functions that satisfy a specific mathematical property. The convention is to use the simplest of all of the functions in the set to characterize the complexity class.

^{1 - Some people argue that it is not incorrect to use non-standard / non-conventional Big O notation. However, that defeats the purpose of using a mathematical notation ... which is the clear communication of mathematical ideas from one person to another. Analogy: if I wrote 1 + 1 is 11, I may be technically correct (using unary notation), but this an epic fail as means of communicating the idea 1 + 1 = 2.}

---

My teacher is asking for the 'precise' amount of executions.

Well:

1. That's NOT Big O.

2. It is not a particularly useful measure, since the actual instruction count on real hardware after real compilation with a real compile will be different.

---

You say:

I believe each line of code has a certain amount of executions

The problem is that the number of "executions" depends on how you define what the primitive operations are, and how you compile the Java code to primitive operations.

For example, there are different ways to compile the nested loops in your example into instructions that will give different numbers of primitive jumps to be performed. (Think loop unrolling and / or a massive switch statement.)

This is illustrated by Nikos's answer. He has done a careful accounting of the instructions (according to his interpretation of what the primitive operations are) and come up with a different formula to your teacher. Who is correct? Probably both ... depending on the assumptions.

Answer 3

You say the answer is O(4N^2 + 5N + 2) , but in fact answer,if reduced to BIG O will be O(N^2).

O(4N^2+5N+2+anythinglessthan N^2) reduces to O(N^2).

I will try to give you a hint if in future you are struck in finding complexities in a loop.

1. Time complexity of a function is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function, in your case sum += i;

2. Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount, in your case inner loop will have complexity O(N) if taken individually.

3. Time complexity of nested loops is equal to the number of times the innermost statement is executed. In your case O(N^k) -> O(N^2)

Combining 1+2+3 will give you the upper bound as O(N^2)