2-D peak finding complexity (MIT OCW 6.006)

Question

In a recitation video for MIT OCW 6.006 at 43:30,

Given an $m \times n$ matrix $A$ with $m$ columns and $n$ rows, the 2-D peak finding algorithm, where a peak is any value greater than or equal to it's adjacent neighbors, was described as:

Note: If there is confusion in describing columns via $n$, I apologize, but this is how the recitation video describes it and I tried to be consistent with the video. It confused me very much.

1. Pick the middle column $n/2$ // Has complexity $\Theta(1)$

2. Find the max value of column $n/2$ //Has complexity $\Theta(m)$ because there are $m$ rows in a column

3. Check horiz. row neighbors of max value, if it is greater then a peak has been found, otherwise recurse with $T(n/2, m)$ //Has complexity $T(n/2,m)$

Then to evaluate the recursion, the recitation instructor says

$T(1,m) = \Theta(m)$ because it finds the max value

$$ T(n,m) = \Theta(1) + \Theta(m) + T(n/2, m) \tag{E1}$$

I understand the next part, at 52:09 in the video, where he says to treat $m$ like a constant, since the number of rows never changes. But I don't understand how that leads to the following product:

$$ T(n,m) = \Theta(m) \cdot \Theta(\log n) \tag{E2}$$

I think that, since $m$ is treated like a constant, it is thus treated like $\Theta(1)$ and eliminated in $(E1)$ above. But I'm having a hard time making the jump to $(E2)$. Is this because we are now considering the case of $T(n/2)$ with a constant $m$?

I think can "see" the overall idea is that a $\Theta(\log n)$ operation is performed, at worst, for m number of rows. What I'm trying to figure out is how to describe the jump from $(E1)$ to $(E2)$ to someone else, i.e. gain real understanding.

Answer 1

As I understand it, it takes $\Theta$(m) time to evaluate all the elements in given column and identify which of those elements is the global maximum. Where the $\Theta (\lg(n))$ comes in is that in the worst case scenario, the algorithm must evaluate $\lg(n)$ columns in the matrix before finding a peak. Total work would then be $\Theta(m\lg(n))$

For example, let's say your matrix has 32 columns and 8 rows.

1. You take the middle column, say column 16. You evaluate it and find that the column's global peak is superseded by an element to the right. You drop columns 1-16, and focus on columns 17-32
2. Find the middle column of the remaining matrix, which is column 24, and you evaluate for a global peak (this is your second column evaluation). You find you need to move to the right. Drop columns 17-24, focus on 25-32.
3. Find the middle (column 28) - you evaluate (third column evaluation), and you find you need to move to the right. Drop columns 25 - 28, and focus on 29 - 32.
4. Evaluate column 30 (fourth evaluation), find you need to move to the right, drop columns 29-30.
5. Evaluate one of the remaining columns (fifth column evaluation), and you're done.

In total, you completed five column evaluations. 5 = $\lg(32)$ = $\lg(n)$ where n is the number of columns in the matrix and lg is log base 2.

Answer 2

the analysis you outline appears to be incorrect. the correct complexity is $O(m)$ where $m$ is the larger dimension of the matrix (either rows or columns). see this other correct analysis for more/better detail. part of the mistake is not defining the recurrence relation $T(n,m)$ in terms of $T(n,m)$ only (which is handled correctly in the paper). the paper shows/uses an infinite series:

$ \begin{eqnarray*} T(n) & = & T \left({n \over 2}\right) + cn \\ T(n) & = & T(1) + cn \left( 1 + {1 \over 2} + {1 \over 4} + {1 \over 8} + \cdots \right) \\ &= & O(n) \end{eqnarray*} $