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 '20 at 17:38
• Hint: What are m and n? Hint: Does crossProduct even know what m and n are? Sep 22 '20 at 18:03
• Thank you @gnat Sep 22 '20 at 18:46
• @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 '20 at 18:56
• 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 '20 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: