How to find the solution of $T(n,m) = T((n-1),m) + T(n,(m-1))$ in terms of big $O$ notation?

Question

I would like to solve the recurrence $T(n,m) = T((n-1),m) + T(n,(m-1))$. I think the solution is $$O(2^{n+m})$$ because in every step you can reduce either $n$ or $m$ by one or not, but I can not really come up with a proper mathematical argument for this.

Answer 1

We can obtain the solution explicitly using generating functions. Define $$G_n (t):= \sum_{m=0}^{\infty}T_{n,m}t^m,$$

and now multiply the recurrence by $t^m$ and sum: $$\sum_{m=1}^{\infty}T_{n,m} t^m=\sum_{m=1}^{\infty}T_{n-1,m} t^m+\sum_{m=1}^{\infty}T_{n,m-1} t^m.$$ We sum from $m=1$ because otherwise we the $T_{n,m-1}$ would give us $T_{n,-1}$ for $m=0$. All in all we have $$G_n(t)-T_{n,0}=G_{n-1}(t)-T_{n-1,0}+ t\cdot G_n(t),$$ and now some initial values would come in handy! I'll assume that $T_{n,0}=0$ for all $n$ if you don't mind!. This gives a recurrence relation for the functions: $$G_n(t)=\frac{1}{1-t}G_{n-1}(t)$$ and just iterate to find $G_n(t)=(\frac{1}{1-t})^n G_{0}(t)$. Again, we're missing initial conditions badly, but $T_{0,m}=1$ for all $m$, just so that $$G_0(t)=0+\sum_{m=1}^{\infty} 1\cdot t^m=\frac{t}{1-t}$$ for |t|<1. It's a generating function, we don't really care for convergence, and note that our previous constraint that all $T_{n,0}=0$ left us with no choice but to say that $T_{0,0}=0$, I think?

Altogether we expand $G_n(t)$ into a binomial series to get: $$G_n(t)=\left(\frac{1}{1-t}\right)^n \frac{t}{1-t}=\frac{t}{(1-t)^{(n+1)}}=t\cdot \sum_{m=0}^{\infty} {m+n\choose m}\cdot t^m,$$

which means $$T_{n,m}={n+m-1\choose m}.$$ And in fact Mathematica confirms that it satisfies the recurrence!

Answer 2

It's faster than $O(2^{n+m})$ - note that if $n=1$, time complexity is $O(m)$, not $O(2^m)$.

I don't see the exact answer, but I do see good lower and upper bounds:

$O(2^{min(m,n)}) \leq O(T) \leq O(2^{n+m})$

Think of a binary tree generated by $T$. First node has parameters $(m,n)$, and it has two children $(m-1,n)$ and $(m,n-1)$, and so on. A node has one (or zero) children iff one (or both) of its arguments are zero.

Note that minimum length of a leaf-to-root path is $min(m,n)$ and maximum is $m+n$. Therefore total number of nodes is between $2^{min(m,n)}$ and $2^{n+m}$. Can anybody improve it?..

PS Usually this kind of problems are solved using dynamic programming, which reduces complexity to polynomial.

Answer 3

Looking at this as a sum in reverse, suppose that our "base value" is at $T(1,1)$. To get to $T(n,m)$, follow Pascal's Triangle, since $T(n,m)=T(n-1,m)+T(n,m-1)$, exactly matching the definition of Pascal's Triangle. Therefore, we have

$$T(n,m)=T(n-1,m)+T(n,m-1)={n+m-1\choose m}T(1,1)$$

This is a bit tricky, but if you notice that $n$ and $m$ are equidistant from $n+m\over 2$, then it is clear that we have ${n+m-1\choose m}={n+m-1\choose n}$, so the formula isn't actually "biased" towards $n$ or $m$, even though it looks that way. The $-1$ means that we get $T(1,1)=\binom 11T(1,1)$ as we would expect...