2

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

    while x > 0:
        x -= 1
        total += x

    return total

Question : What is the number of steps it will take to run Program 1 in the best case? Express your answer in terms of n, the size of the input x

Answer : Best case : 3003 and Worst Case : 5n+3003

I am confused with the answer 3003 because according to me the problem's best case would be if x =-1 and other statements execute which have a constant amount of time .hence statement 

total =0   // takes a constant amount of time 1

for i in range(1000):
    total += i        // takes 1000*1 amount of time


return total   // takes constant of time 1

Hence the answer should be 1000+2=1002

Any help with proper explanation will be highly appreciated ..

Turix
  • 4,470
  • 2
  • 19
  • 27
Diljit PR
  • 301
  • 3
  • 14
  • Can you link to that course? – Tim Pietzcker Jul 17 '14 at 05:38
  • @TimPietzcker https://www.edx.org/course/mitx/mitx-6-00-1x-introduction-computer-1841 – Diljit PR Jul 17 '14 at 05:40
  • 1
    Your code is not indented correctly and you don't explain the question properly. According to your code worse case is when x -> infinite. and best case is when x < 1. The sum 3003 is not depended on x at all! The link to the course is not helpful - but a link to the original question will be. – Nir Alfasi Jul 17 '14 at 05:41
  • @alfasin question edited ..and i have already copied the question from the course dashboard.. – Diljit PR Jul 17 '14 at 05:43
  • 1
    and *everything* I wrote before still applies... – Nir Alfasi Jul 17 '14 at 05:44
  • It is just a conjecture of mine, somebody please correct me if I am wrong: You summed up to 1002 which should be 1003 because the condition `x > 0:` will be executed at-least once. Also, shorthand += is `total = total + i;` which is an assignment+addition so multiply 1000 with 2 instead of 1. – Abdul Fatir Jul 17 '14 at 05:46
  • yeah infact 1003 ..thanks for the correction @AbdulFatir – Diljit PR Jul 17 '14 at 05:47
  • @alfasin Question edited with snapshot..please see to it.. – Diljit PR Jul 17 '14 at 05:49
  • okay so now the indent part has been taken care of. What about the rest ? – Nir Alfasi Jul 17 '14 at 05:53
  • it would be better if we have right `title` for this question – Nava Jul 17 '14 at 06:38

1 Answers1

3

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:

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

    while x > 0:               // counts as 1 + N  (note: so when x <= 0, still counts as 1)
        x -= 1
        total += x

    return total               // counts as 1

...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 1
    for i in range(1000):      // counts as 1 * 1000
        total += i             // counts as 2 * 1000

    while x > 0:               // counts as 1 + N
        x -= 1                 // counts as 2 * N
        total += x             // counts as 2 * N

    return 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.

Community
  • 1
  • 1
Turix
  • 4,470
  • 2
  • 19
  • 27
  • You considered assignment and condition testing as 2 seperate operations inside the for loop ..so according to me including i=1,i<1000,i+=1 these are 3 separate operations and takes a constant amount of time..Shouldn't the answer be 1000*4+3=4003? Correct me if i am wrong! – Diljit PR Jul 17 '14 at 06:11
  • 1
    @DiljitPR The *initialization* of `i` does not need to happen 1000 times. And the first time through the loop, instead of *incrementing* `i`, the value is just initialized. [Note: depending on the implementation, there *might* be a need for an additional step for the *last* time through the loop (if, for example, `i` gets incremented to 1001 immediately prior to exiting the loop), which could lead to a count of 3004 instead of 3003, but I *think* in Python, when iterating over a range, this isn't necessary.] – Turix Jul 17 '14 at 06:18
  • @DiljitPR Although I consider my original explanation "correct", I am going to modify my answer after considering the *worst* case (which I know you didn't ask about but is inconsistent with the logic I used for my answer). – Turix Jul 17 '14 at 06:25
  • This helps ..If possible can u try and make an explanation for the worst case scenario? – Diljit PR Jul 17 '14 at 06:41
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/57467/discussion-between-diljit-pr-and-turix). – Diljit PR Jul 17 '14 at 06:50
  • Heres the answer :In the best case scenario, x is less than or equal to 0. We first execute the assignment total = 0 for one step. Next we execute the for i in range(1000) loop. This loop is executed 1000 times and has three steps (one for the assignment of i each time through the loop, as well as two for the += operation) on each iteration. We next check if x > 0 - it is not so we do not enter the loop. Adding one more step for the return statement, in the best case we execute 1 + 3*1000 + 1 + 1 = 3003 steps. – Diljit PR Jul 17 '14 at 07:29
  • @DiljitPR Thanks. I think that agrees with my update. Did you not have access to that prior to posting your question? – Turix Jul 17 '14 at 07:40