3

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):
    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.


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

6
  • 1
    Does this answer your question? Big-O for nested loop
    – gnat
    Sep 22 '20 at 17:38
  • 2
    Hint: What are m and n? Hint: Does crossProduct even know what m and n are?
    – user253751
    Sep 22 '20 at 18:03
  • Thank you @gnat Sep 22 '20 at 18:46
  • 1
    @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
  • 1
    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
1

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. 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.