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

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

StackExchange Computer Science Q#10141, answer score: 2