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.