Solving a multivariate equation for asymptotic complexity

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$$?

• I would try to analyze it for the three cases $n < m$, $n = m$ and $n > m$. Clearly if $n=m$ then they have the same rate of change and it breaks down to $T(n) = 2T(n/2) + c_1 \log n + c_1$. See how it works for the other two cases as well. You can also assume $n$ and $m$ are powers of 2 if that makes it easier.
– ryan
Commented May 18, 2020 at 14:49
• What is the significance of those three cases? That seems somewhat arbitrary - I might as well analyze the cases $n < 2m$ or $n < m^2$. I don't see how checking these regions of the domain will help - I already have the recurrence relation. Commented May 18, 2020 at 15:14
• Since they're both decreasing at the same rate (namely $x/2$) the one which is greater will determine how many times the function recurses. If you can determine that, you can get out a summation bounded by how many times the function recurses.
– ryan
Commented May 18, 2020 at 15:21
• What are the base cases? Commented May 18, 2020 at 16:04

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)$$.
• Is it safe to assume that $c_1 = 0$ ? Why? Commented May 18, 2020 at 17:52
• Since $\log n + 1 = \Theta(\log n)$. Commented May 18, 2020 at 17:53
• I seem to have missed a case - $T(m,\ 1) = T\bigl(\frac{m}{2}, 1 \bigr) + c_1$. I've updated my question to show the base cases. Following your derivation, I get $T(2^a, 2^b) = 2^{b+1} - 2(b + 1) + a$ in the region where $a >= b$. Does this still give $T(m, n) = \Theta(n)$ ? I don't follow how you got from $T(2^a, 2^b) = 2^{b+1} - (b + 2)$ to $T(m, n) = \Theta(n)$. Commented May 19, 2020 at 6:40
• Oh, I see. $2^{b+1} - (b + 2) = 2 n - (log(n) + 2)$, which is $\Theta(n)$. So considering my missed case, $2^{b+1} - 2(b + 1) + a = 2n - 2(log(n) + 1) + log(m)$. So that should be $\Theta(n + log(m))$? Commented May 19, 2020 at 6:50