# Nested loop complexity

I am working through MIT 6.006 OpenCourseWare as taught in Fall 2011. Problem 1.2c asks for the time complexity of an algorithm1 which finds a peak element (i.e. all neighbors are less than or equal) of an M x N matrix. My complexity analysis does not match theirs and appears to hinge on the complexity of a nested loop.

The algorithm creates a cross which divides the matrix into four "subproblems". It finds the max on the cross, checks neighbors, and recurses as needed:

``````def algorithm3(problem, bestSeen = None, trace = None):
# if it's empty, we're done
if problem.numRow <= 0 or problem.numCol <= 0:
return None

midRow = problem.numRow // 2
midCol = problem.numCol // 2

# first, get the list of all subproblems
subproblems = []

(subStartR1, subNumR1) = (0, midRow)
(subStartR2, subNumR2) = (midRow + 1, problem.numRow - (midRow + 1))
(subStartC1, subNumC1) = (0, midCol)
(subStartC2, subNumC2) = (midCol + 1, problem.numCol - (midCol + 1))

subproblems.append((subStartR1, subStartC1, subNumR1, subNumC1))
subproblems.append((subStartR1, subStartC2, subNumR1, subNumC2))
subproblems.append((subStartR2, subStartC1, subNumR2, subNumC1))
subproblems.append((subStartR2, subStartC2, subNumR2, subNumC2))

# find the best location on the cross (the middle row combined with the
# middle column)
cross = []

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

crossLoc = problem.getMaximum(cross, trace)
neighbor = problem.getBetterNeighbor(crossLoc, trace)

# update the best we've seen so far based on this new maximum
if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen):
bestSeen = neighbor
if not trace is None: trace.setBestSeen(bestSeen)

# return if we can't see any better neighbors
if neighbor == crossLoc:
if not trace is None: trace.foundPeak(crossLoc)
return crossLoc

# figure out which subproblem contains the largest number we've seen so
# far, and recurse
sub = problem.getSubproblemContaining(subproblems, bestSeen)
newBest = sub.getLocationInSelf(problem, bestSeen)
if not trace is None: trace.setProblemDimensions(sub)
result = algorithm3(sub, newBest, trace)
return problem.getLocationInSelf(sub, result)
``````

The instructor provides the complexity for `getMaximum` as O(len(locations)), `getBetterNeighbor` and `getLocationInSelf` as O(1), `getSubproblemContaining` as O(len(boundList)), and all trace calls as O(1). The `crossProduct` is computed as:

``````def crossProduct(list1, list2):
for a in list1:
for b in list2:
``````

The solution states, "a single call of the function (not counting the recursive call) does work proportional to m + n." I don't understand this.

Isn't `crossProduct` O(mn)?

My reasoning is that for an M x N matrix, `getMaximum` must traverse the dividing cross (one row, one column) which contributes O(m + n). The `getSubproblemContaining` contributes something linear, O(m) or O(n). Everything else besides `crossProduct` is O(1), the complexity of `crossProduct` not being provided, so that the recurrence relation is

``````T(m, n) = O(mn) + O(m + n) + cO(n) + T(m/2, n/2)   for some constant c
= O(mn) + T(m/2, n/2)
``````

The recurrence reduces via the geometric series to O(m + n),

``````T(m, n) = O(mn) + O(m + n)
= O(mn)
``````

which yields T(n,n) = O(n^2). The solution provided is O(n). The `crossProduct` term appears to be the discrepancy.

1 The algorithm/code implementation is written by the instructor. All Pythonic style errors are theirs (and likely made for pedagogical reasons).

– gnat
Sep 22, 2020 at 17:38
• Hint: What are m and n? Hint: Does crossProduct even know what m and n are? Sep 22, 2020 at 18:03
• @user253751 I see the issue. crossProduct is not taking in m and n, but rather a point (represented as a list for technical reasons) and a range. This means crossProduct will run in linear time as the point is constant and only the range must be traversed. The O(mn) doesn't apply and the run time of crossProduct is then accounted for in the cO(n) term. Sep 22, 2020 at 18:56
• @user253751 If you submit an answer, I will accept it. These types of questions are awkward for SO. I sincerely appreciate those who read this tome. Sep 22, 2020 at 18:58
• Using a cross product function for a single element is quite unidiomatic. More explicit Python code would probably use a comprehension, e.g. `cross.extend((midRow, i) for i in range(problem.numCol))` which makes it quite clear that this is linear, and that `len(cross)` will be `numCol + numRow`.
– amon
Sep 22, 2020 at 19:44

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

When you say that this function:

``````def crossProduct(list1, list2):
for a in list1:
for b in list2:
``````

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. It would be easier if we said that crossProduct has O(ab) complexity 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 have O(1n + m1) = O(n + m) complexity.