educative.io

Educative

Unclear about the calculation of Big O of for loop

**How did we arrive at the conclusion that 3x(n+1) operations are happening when for loop performs the ‘test’ operation (comparison operator)? or the number of increment operations = 3n? Specifically how did they arrive at the conclusion that the operations are multiplied by 3? **

Hi PS_Developer ,

This is Maida from Educative.

Firstly to simplify the things we are assuming that each primitive operation will take one unit of time. Primitive operation includes addition, subtraction or multiplication, etc. The test operation (i < n) will:

  • Read the current value of the variables i (1 primitive operation)
  • Read the current value of the variables n (1 primitive operation)
  • Then compare the values of i and n (1 primitive operation)

So, that’s three primitive operations for checking the condition. Now the condition is checked for n = 0 to n = 10. It means the condition is checked 11 times in total which can be written as n+1. Since the condition is checked n+1 times in total and it takes 3 primitive operations that’s why we can say that for loop takes 3x(n+1) operations for testing.

Similarly,

The increment (i++) operation:

  • must read the current value of the variable i (1 primitive operation)
  • add 1 to it (1 primitive operation)
  • store the result back in the variable i (1 primitive operation)

That’s three primitive operations. Whereas increment operation is performed for n == 0 to n == 9 which means it is done 10 times (or n times) in total. This is the reason that we can say for loop takes 3n operations for testing.

We hope Educative has inspired to further your learning, and please drop us a note if you have any other questions or concerns.

Best Regards,
Maida | Developer Advocate
educative.io

1 Like