Return to Revisions

Don't forget, what n and m actually are.

When you say that this function:

def crossProduct(list1, list2):
    answer = []
    for a in list1:
        for b in list2:
            answer.append ((a, b))
    return answer

takes O(mn) time, what are m and n? Well, m is the size of list1 and n is the size of list2 (or vice versa).

When you say that algorithm3 takes O(mn) time, what are m and n? Well, m is the number of rows and n is the number of columns (or vice versa).

Hang on! Those aren't the same thing! We should use different names for different variables. So it would be easier if we said that crossProduct takes O(ab) time where a is the size of list1 and b is the size of list2 (or vice versa). You can't give two different things the same variable name and then just assume they are the same thing.

So what are a and b?

cross.extend(crossProduct([midRow], range(problem.numCol)))
cross.extend(crossProduct(range(problem.numRow), [midCol]))

Okay, so we call it once with a=1 and b=n, and we call it again with a=m and b=1. So these two calls together take O(1n + m1) = O(n + m) time.