Exercise 2

试题部分几乎全错（题目链接）。

举个例子：

What is the number of steps it will take to run Program 2 in the worst case? Express your answer in terms of n, the size of the inputx

def program2(x):
    total = 0
    for i in range(1000):
        total = i

    while x > 0:
        x = x//2
        total += x

    return total

Exercise 3

Program 1:

def program1(L):
    multiples = []
    for x in L:
        for y in L:
            multiples.append(x*y)
    return multiples

What is the number of steps it will take to run Program 1 in the worst case? Express your answer in terms of n, the number of elements in the listL. You can assume list appending takes 1 step.

answer:

In the worst case scenario,Lis a long list. In this case we go through the loopfor x in Lntimes. Every time through this loop, we execute an assignment of a value tox, and then the inner loopfor y in L. The assignment takes 1 step on each iteration; how many steps does the inner loop take on each iteration?

The inner loop has three operations (assignment of a value to y, x*y, and list appending). So the inner loop executes 3*n times oneach iterationof the outer loop. Thus the nested loop structure is executed n * (3*n + 1) = 3*n**2 + n times!

Adding in two steps (for the first assignment statement, and the return statement) we see that in the worst case, this program executes 3*n**2 + n + 2 steps.