Confused With Answer About Best/worst Case Time For Python Function

This is a short problem from edx's course Introduction to Computer Science and Programming using Python. def program1(x): total = 0 for i in range(1000): total += i

Solution 1:

If I understand your question correctly, I think the key to understanding the answer is that the line for i in range(1000): is doing two things [ed: see update below] each time through the loop that you neglected to count: first, it is incrementing the variable i and second, it is checking it against the maximum value (1000) to see if the loop is finished. So each pass through the loop should count as 3 operations.

Finally, even if the loop is skipped, it still takes one operation to decide to do this, that is to check x against 0 in the line: while x > 0:.

This is how it would be accounted in the best case:

defprogram1(x):
    total = 0                  // counts as1for i inrange(1000):      // counts as2 * 1000
        total += i             // counts as1 * 1000while x > 0:               // counts as1 + N  (note: so when x <= 0, still counts as1)
        x -= 1
        total += x

    return total               // counts as1

...which adds up to 3003.

---

Update:

Given that the worst case answer provided to you is 5n + 3003, I must modify my answer.

That means that the -= and += operations within the while loop must be being counted as two separate operations (the increment or decrement and the assignment). If so, then the += operation within the for loop must also count as 2 operations. And if that is the case, the only way to make the numbers agree with the provided answer is if the accounting is like this:

def program1(x):
    total =0// counts as 1for i in range(1000):      // counts as 1 * 1000
        total += i             // counts as 2 * 1000while x > 0:               // counts as 1 + N
        x -= 1// counts as 2 * N
        total += x             // counts as 2 * Nreturn total               // counts as 1

I personally disagree with counting the += and -= as two things, in the abstract sense, because I know that they can be done as a single operation in assembly (assuming all values are in registers), but in Python they are actually two operations. (See the 4th answer in the link below for more on this.)

To accept this accounting, you must also accept that the line for i in range(1000): only counts as one operation each time through the loop. Upon realizing that I was wrong above, I found this answer here which helps with understanding that. Basically, this is because the upper bound as well as the iterated elements themselves of the loop are fixed.