9
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Apass.Jack Aug 21 '18 at 14:04

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.