time complexity of variable loops

Question

hi, i want to try to calculate the O(n) of my program (in python). there are two problems:

1: i have a very basic knowledge of O(n) [aka: i know O(n) has to do with time and calculations]

and

2: all of the loops in my program are not set to any particular value. they are based on the input data.

Answer 1

The n in O(n) means precisely the input size. So, if I have this code:

def findmax(l):
    maybemax = 0
    for i in l:
        if i > maybemax:
            maybemax = i
    return maybemax

Then I'd say that the complexity is O(n) -- how long it takes is proportional to the input size (since the loop loops as many times as the length of l).

If I had

def allbigger(l, m):
    for el in l:
        for el2 in m:
            if el < el2:
                return False
    return True

then, in the worst case (that is, when I return True), I have one loop of length len(l) and inside it, one of length len(m), so I say that it's O(l * m) or O(n^2) if the lists are expected to be about the same length.

Answer 2

Try this out to start, then head to wiki:

• Plain English Explanation of Big O Notation