# 2-D peak finding complexity (MIT OCW 6.006)

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.

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.

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*}$

• This answer is, in fact, off the question! The OP talks about the algorithm in the recitation video MIT OCW 6.006 while this answer talks about a different algorithm. In particular, the analysis outlined by OP is correct with respect to the algorithm in that video. Commented Aug 21, 2018 at 14:04