0

I have an algorithms recurrence $$T(m,n) = T(m/2,l) + T(m/2,n-l) + \mathcal{O}(mn)$$ where $0 \leq l \leq n$.

If $l = n/2$ is fixed, then it is quite easy to show that $T(m,n) = \mathcal{O}(mn)$.

However, in my problem, $l$ is not a constant, and it can vary throughout each recursive call. It turns out that $T(m,n) = \mathcal{O}(mn)$ even in this case, and the idea seems to be based on the fact that for the two sub-problems, $l + (n-l) = n$, but I am not sure how to turn this into a proof.

user308485
  • 1,229
  • 7
  • 13

1 Answers1

1

Based on comments I'm adjusting the answer. We have the recurrence:

$$ T(m, n) = T \left( \frac{m}{2}, l \right) + T \left( \frac{m}{2}, n - l \right) + k m n $$

where $l$ is some arbitrary value between $0$ and $n$, inclusive, and $k$ is a constant. We prove $T(m, n) = O(mn)$ using induction. We assume $T(m, n) \leq cmn$ for some constant $c$ and substitute into the recurrence and then apply induction:

$$ T(m, n) = T \left( \frac{m}{2}, l \right) + T \left( \frac{m}{2}, n - l \right) + k m n $$

$$ T(m, n) = c \frac{m}{2} l + c \frac{m}{2} (n - l) + k m n $$

$$ T(m, n) = c \frac{m}{2} n + k m n $$

$$ T(m, n) \leq c m n $$

which holds when $c \geq 2k$. And so we conclude $T(m, n) = O(mn)$ as you stated.

prcssngnr
  • 1,191
  • Actually, the problem is not a DP problem. The subproblems do not overlap at all, but I believe the O(mn) bound should still hold. Also, I am fairly certain that $l$ can be chosen arbtitrarily (perhaps by an adversary) and the total time would still be at most $O(mn)$. – user308485 Jul 25 '23 at 18:30
  • @user308485 I see. Does that mean that $l$ takes on precisely one value between $0$ and $n$? If this is the case one can use induction to prove the bound. We assume that $T(m, n) \leq cmn$ for some $c > 0$. And so we get: $$ T(m, n) = T\left( \frac{m}{2}, l \right) + T\left( \frac{m}{2}, n - l \right) + mn$$ $$ T(m, n) = c\frac{m}{2}l + c\frac{m}{2}(n - l) + mn$$ $$ T(m, n) = c\left( \frac{m}{2}n \right) + mn $$ $$ T(m, n) \leq cmn $$ Which holds when $c \geq 2$. And so $T(m, n) = O(mn)$. – prcssngnr Jul 25 '23 at 19:09
  • No, and I apologize for this not being clear in the problem. $l$ is a value that is different for each recursive call, in fact it is computed in the recursive call itself. What is known about $l$ is that it is guaranteed to be between $0$ and $n$ no matter which node of the recursion tree are in. – user308485 Jul 25 '23 at 19:13
  • I've modified the answer based on your comments. In this answer $l$ is some arbitrary value between $0$ and $n$. – prcssngnr Jul 26 '23 at 10:11
  • 1
    Thanks! It looks completely correct and makes sense. – user308485 Jul 26 '23 at 12:30