calculating number of operations in algorithm

Question

total1 = 0
total2 = 0
n = int( input (' Enter the value of n : '))

for x in range(n+1): 
   total1 += x

for y in range(1 , n): 
   total2 += total1*y

print('total1' , total1)
print('total2' , total2)

1. I am kinda confused if assignment is considered an operation or not
2. I am not sure how to calculate number of operations in a loop for x in range(n+1): total1 += x

How do we calculate number of operations here , is this a n + 2 operation because the loop is n+1 and then total1 +=x is another 1 operation, so n+1+1 = n +2

Please kindly shed some light here. Not to sure on how to calculate this ?

Thank you

Answer 1

You have 3 operations at the beginning:

total1 = 0
total2 = 0
n = int( input (' Enter the value of n : '))

Then for the first loop

for x in range(n+1): 
   total1 += x

you have n + 1 calls of range and n assignments.

For the second loop:

for y in range(1 , n): 
   total2 += total1*y

you have n calls of range + (n-1) multiplications + (n-1) assignments.

So, totally we get:

3 + (n+1) + n + n + 2*(n-1) = 
3*n + 2*n + 4 - 2 = 
5*n + 2

Actually, this calculation is not fully correct as range call is not an atomic operation. But we can ignore it as it doesn't have an inner loop inside the function. Your algorithm has O(n) complexity.

I recommend you to read chapter 3 of the book "Introduction to algorithms" by Cormen et al.