What does Big O notation actually mean, and how do you work out the bound for a given piece of code?
Big O notation is a way of saying how the amount of work grows as the input gets bigger. It is not a measurement of time. It is a shape.
Here is the idea. If you double the size of the input, how much more work does the program do? If the answer is twice as much, then the algorithm is linear and you write it as O of n. If the answer is four times as much, it is O of n squared. If the answer is barely more, it is O of log n.
def count_operations(n, nested):
ops = 0
for i in range(n):
ops += 1
if nested:
for j in range(n):
ops += 1
return ops
So how do you work out the bound? You count the loops.
One loop over n items is O of n. Two loops one after the other are still O of n, because you do the first one and then the second one, so the work is n plus n, which is two n, which grows like n. Two loops one inside the other are O of n squared, because you do the inner loop n times for each of the n rounds of the outer one, so the work is n times n.
So for the function above, the bound is O of n squared when the nested flag is true, and O of n when it is false. You say the worse one, because a bound has to hold for every input.
There are two more rules that make it easier. The first one is that you drop the constants, so three additions in a loop is still O of n. The second one is that you drop the terms that are smaller as the input grows, so n squared plus n is just O of n squared.
So the rule to remember is this. Count the loops, multiply the ones that are nested, add the ones that are in a row, and then throw away everything except the biggest piece.