python running time question big o notation

Question

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) 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

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

(c) x = 1 while x < n: x = x * 2 print x

Can anyone tell me how this works in each of the situations? For each one i need the running time, reasoning and what the code accomplishes.

Thank You!

Answer 1

To get the running time, run the fragment and time how long it takes to run. If you can't manage that much on your own, I think you will struggle to understand big-O notation

Answer 2

Here's how you can approach it. Find the statements that run in constant time (I'll do the second one for you, you can do the rest).

The constant time statements are:

x = x + j/float(i*(i+1))

What I mean by that is that they take the same amount of time no matter what the value of n is.

Now you need to figure out how n affects that constant time. Since you're running inside a loop 1..n which is itself running inside a loop 1..n, the constant time statements will execute n * n times. Hence the complexity is O(n*n). You figure this out by asking yourself how the input value n affects the running time.

Armed with that, the first one should be a walk in the park for you. The third one may end up being so difficult that you would prefer to trip over a log and land flat on your face.

^{There's a hint in there and it's not the word "face".}

As to what the code accomplishes in each case, you should run it, after inserting suitable print statement inside the loop to show you how affected variables change each time through.

For example, part 3 will start x at 1 and double it until it's greater than or equal to n. You don't have to be a rocket scientist to figure out this will give you the smallest power of two that's greater than or equal to n. But, by all means, test it (with different values of n below):

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

---

To get running time, you have to either have a very fine grained measuring tool or you have to run it many times. If you're on Linux, you can use the time command:

$ time python qq.py
128
real    0m0.107s
user    0m0.030s
sys     0m0.093s

You should run it ten times for each input value, throw away the fastest and slowest and average the other 8. This will give you a reasonable average, without outliers.

Answer 3

Big O notation is a way to talk about the running time of your program over a wide range of different datasets. It expresses your running time in terms of some important feature of the data that the program (or program fragment) is processing.

There are two parts to getting O notation correct. The first is to pick the correct attribute of the dataset you're processing, and the second is to figure out how that attribute relates to total running time.

Both choices must be made with an eye towards being able to express the total time the program will take as an upper bound. The upper bound will be expressed as a function of the feature of the data set you have chosen.

Lets pick an easy one.

Suppose you have a list of items you want to add by hand. First, what is the most important feature of the list in determining how long it's going to take you to add? Well, it could be one of two things, it could either be some quality of the numbers you are adding, or some quality of the list as a whole. For example, it might be how many digits the numbers have, or how many items there are in the list.

As an additional constraint, I'll add that none of the numbers are larger than 1 billion, now what's the most important feature? Well, the size of the numbers is no longer a concerned because the size is tightly constrained. It can't, for example, be possibly infinite. So it's probably how long the list is.

Next is determining your bound function. How much longer will it take you to add a list of 30 numbers vs. a list of 10 numbers. Maybe 3 times as long? How about a list of 60 numbers? Twice as long as 30? That means your function varies linearly with how many numbers you have. THat means the problem of adding up a list of numbers by hand is an O(n) problem where n is the number of items in the list.

This is logic you can apply to the program snippets you've asked us to do for you. Think through what the code is doing, and what the main issue is for running time. Imagine the possible ranges for the values involved and figure out which ones might be arbitrarily large and figure out how the program running time relates to their value.