I am working through MIT 6.006 OpenCourseWare as taught in Fall 2011. Problem 1.2c asks for the time complexity of an algorithm which finds a peak element (i.e. all neighbors are less than or equal) of an M x N matrix. My solution 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):
answer = ()
for a in list1:
for b in list2:
answer.append ((a, b))
return answer
```

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.