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.


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

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

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 &quot;see&quot; 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.
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) &amp; = &amp; T \left({n \over 2}\right) + cn \\
 T(n) &amp; = &amp; T(1) + cn \left( 1 + {1 \over 2} + {1 \over 4} + {1 \over 8} + \cdots \right) \\
&amp;= &amp; O(n)
\end{eqnarray*}
$