2-D peak finding complexity (MIT OCW 6.006)
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*}
$