Solving a multivariate equation for asymptotic complexity

Question

I have a function $f(m, n)$ with time complexity $T(m, n)$ characterized by the recurrence relation

$$\begin{align} T(m,\ n) &= 2T\bigl(\frac{m}{2}, \frac{n}{2}\bigr) + c_0 \log n + c_1.\\ T(m,\ 1) &= T\bigl(\frac{m}{2}, 1 \bigr) + c_1 \\ T(0,\ n) &= 1 \\ T(m,\ 0) &= 1 \end{align}$$

I can see that for fixed $m$, this is $O(n)$, and for fixed $n$, this is $O(m)$. But I don't see how I can get an expression that characterizes the performance in terms of variable $m$ and $n$.

How can I solve this to find the asymptotic complexity in terms of $m$ and $n$?

Answer 1

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) &= b + 2(b-1) + 4(b-2) + \cdots + 2^{c-1}(b-c+1) \\ &= (1+2+\cdots+2^{c-1})b - 2^1 (1) - 2^2 (2) - \cdots - 2^{c-1} (c-1) \\ &= (2^c-1)b - 2^c c + 2(2^c-1) \\ &= 2^c(b+2-c) - (b + 2). \end{align} In other words, $$ T(2^a,2^b) = \begin{cases} 2^{b+1} - (b+2) & \text{if } a \geq b, \\ (b+2)(2^a-1) - a2^a & \text{if } b \geq a. \end{cases} $$ When $m \geq n$, this gives $T(m,n) = \Theta(n)$, and when $n > m$, we get $T(m,n) = \Theta(m\log (n/m)+m)$.