educative.io

Execution times of comparison in Nested Loop with Subtraction

Courses
,
#1

Hello,

In the solution breakdown of Solution Review: Big O of a Nested Loop with Subtraction , it says that var >= 1; is executed n/3 + 1 times in the outer for-loop:

int n = 10;
...
for (int var = n; var >= 1; var = var - 3) {
    ...
}

but I don’t see how that is calculated.

If I use n = 10 then var would be compared like this:

  1. First iteration: 10 >= 1
  2. Second iteration: 7 >= 1
  3. Third iteration: 4 >= 1
  4. Fourth iteration: 1 >= 1
  5. Fifth iteration: -2 >= 1

If it’s actually n/3 + 1 as the solution suggests, for n = 10 it would be 10/3 + 1 ~ 4 which is not correct since the comparsion was made five times, the fifth time is to exit the loop.

So I think the number of executions for var >= 1 is n/3 + 2, am I wrong? if so, can somebody explain me how n/3 + 1 was calculated?

Thank you

3 Likes
#2

Hi,
I came to the same conclusion as you.
I also think n/3 + 2; is the correct number of executions for var >= 1; and n/3 + 1 for System.out.println("Pie: " + pie );

1 Like
#3

Thank you for confirming that. I know that constant doesn’t make a difference in the end but I was confused since we’re learning to analyze the execution.

1 Like
#4

I remembered the examples where there are cases, such as if n is divisible by 3, n%3 = 0 then there are n/3 executions but if n is not divisible by 3, then there are n/3 steps. so both cases are correct for analysis purposes and lead to the same O(n^2)

Course: https://www.educative.io/courses/big-o-notation
Lesson: Educative: Interactive Courses for Software Developers