Big-Oh bound of a recursive function with two variables [closed]

Question

My goal is to obtain the Big-Oh bound of the following recursive function with two variables:

$$T(n,m) = T(n, m-1) + T(n-1,m)+1$$

As initial conditions, $T(0,m)=1$ and $T(n, 0)=1$ for $m \geq 0$ and $n \geq 0$, respectively. Then, I think $T(n,m) \in O(2^{n+m})$ which can be proved as follows:

Proof:

• Let's prove $T(n, m) \leq 2 \times 2^{n+m} - 1$ by induction.
  • Base cases: $T(0, m) = 1 \leq 2 \times 2^{m} -1$ and $T(n, 0) = 1 \leq 2 \times 2^{n} -1$ for $n,m \geq 0$
  • Inductive step
    • Assume $T(k, p) \leq 2 \times 2^{k+p} - 1$ for arbitrary $k$ and $p$. Then, there two next steps: $T(k+1, p)$ and $T(k, p+1)$.
    • Case 1) $T(k+1, p) = T(k+1, p-1) + T(k, p) + 1$ by the recursion. Using the above assumption, $T(k+1, p) \leq 2\times 2^{k+p+1} - 1$; thus, $T(k+1, p)$ holds true.
    • Case 2) $T(k, p+1)$ also holds similarly to Case 1.
  • Hence, $T(n, m) \leq 2 \times 2^{n+m} - 1 \in O(2^{n+m})$ .

My questions are

• Are there errors in the above proof?
• Are there tighter bounds than $O(2^{n+m})$?

Answer 1

A simple and exact value of $T(n,m)$ can be computed by the following simple substitution. $$ C(n+m,m):=\frac{T(n,m)+1}2 $$ Then your recursive function becomes $$ C(n+m,m)=C(n+m-1,m-1)+C(n+m-1,m) $$ with the initial condition $C(m,m)=C(m,0)=1$. As you can see, this is the recursive formula for the binomial coefficient and thus $$ C(n,m)={{n}\choose{m}}, ~~T(n,m)=2{{n+m}\choose {m}} - 1. $$

If you use a very loose bound ${n+m\choose m} \le 2^{n+m}$ then you have $T(n,m)=O(2^{n+m})$ as you showed. For better bounds, you may use other inequalities in Wikipedia page.