Python and Figuring out (Big-O) Running time

Question

Hey can anyone help me with my homework question to do with python and running time please? This is the question below:

In each code fragment given below, determine the number of steps and describe what the code accomplishes, i.e., what value of x has been output based on the value of the integer n. Assume the value of n has already been set. State your running times using the big-O notation. (Remember to throw away leading constants and lower-ordered terms!)

(a)

Python program:

x = 0
a = 6
b = 6
c = 1
for i in range(2*n):
    x = x + c
    c = c + b
    b = b + a
    print x

Running time:

Justification:

What does this code accomplish?

---

(b)

Python program:

x = 0
for i in range(1,n):
    for j in range(1,n):
        x = x + j/float(i*(i+1))
print x

Running time:

Justification:

What does this code accomplish?

---

(c)

Python program:

x = 1
while x < n:
    x = x * 2
print x

Running time:

Justification:

What does this code accomplish?

I dont know how to figure out the running time or what it means by justification and what the code accomplishes. Can anyone help me out please?

Answer 1

Without giving you the answer, count the number of for loops or while loops. If they're nested this counting is multiplicative. That is, for a given n how many loops will the program iterate?

Start simple. First do the case of n = 2. Then do n = 3. Look at the pattern. This is a brute force but if you go back up to stare at the loop counting you can determine a few things:

• if n = 2 yields 4 and n = 3 yields 6 then it is a linear dependency on n
• if n = 2 yields 4 and n = 3 yields 9 then it is a quadratic dependency on n

• if n = 2 yields 4 and n = 3 yields 28 then it is more than likely an n cubed relationship. . . .

  and so on, and so on...

Answer 2

Unless I'm missing something, (c) is an infinite loop so asking for running time is moot.