1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – ryan May 18 '20 at 14:49
  • $\begingroup$ 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. $\endgroup$ – Dr. John A Zoidberg May 18 '20 at 15:14
  • $\begingroup$ 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. $\endgroup$ – ryan May 18 '20 at 15:21
  • $\begingroup$ What are the base cases? $\endgroup$ – Yuval Filmus May 18 '20 at 16:04
3
$\begingroup$

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)$.

$\endgroup$
5
  • $\begingroup$ Is it safe to assume that $c_1 = 0$ ? Why? $\endgroup$ – Dr. John A Zoidberg May 18 '20 at 17:52
  • $\begingroup$ Since $\log n + 1 = \Theta(\log n)$. $\endgroup$ – Yuval Filmus May 18 '20 at 17:53
  • $\begingroup$ 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)$. $\endgroup$ – Dr. John A Zoidberg May 19 '20 at 6:40
  • $\begingroup$ 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))$? $\endgroup$ – Dr. John A Zoidberg May 19 '20 at 6:50
  • $\begingroup$ You changed the question. I'll let you work out the updated answer on your own. $\endgroup$ – Yuval Filmus May 19 '20 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.