Solving a multivariate equation for asymptotic complexity
Suppose for simplicity that $m=2^a$, $n = 2^b$, $c_0=1$, $c_1=0$, and the base cases are $T(1,\cdot) = T(\cdot,1) = 0$. Then
$$
T(2^a,2^b) = 2T(2^{a-1},2^{b-1}) + b = 4T(2^{a-2},2^{b-2}) + b + 2(b-1) = \cdots
$$
The number of summands is $c = \min(a,b)$, and using this notation we obtain
\begin{align}
T(2^a,2^b) &amp;= b + 2(b-1) + 4(b-2) + \cdots + 2^{c-1}(b-c+1) \\ &amp;=
(1+2+\cdots+2^{c-1})b - 2^1 (1) - 2^2 (2) - \cdots - 2^{c-1} (c-1) \\ &amp;=
(2^c-1)b - 2^c c + 2(2^c-1) \\ &amp;=
2^c(b+2-c) - (b + 2).
\end{align}
In other words,
$$
T(2^a,2^b) =
\begin{cases}
2^{b+1} - (b+2) &amp; \text{if } a \geq b, \\
(b+2)(2^a-1) - a2^a &amp; \text{if } b \geq a.
\end{cases}
$$
When $m \geq n$, this gives $T(m,n) = \Theta(n)$, and when $n &gt; m$, we get $T(m,n) = \Theta(m\log (n/m)+m)$.