# How to derive time complexity of the Recurrence Relation - T(n,m) = T(n-1,m) + T(n,m-1) + c

I know that, T(n,m) = T(n-1,m) + T(n,m-1) + c it's the recurrence equation of Longest Common Subsequence algorithm. And the time complexity of the LCS in case of recursive method is O(2^n+m).

The base condition is: when m or n = 0, T(m,n) = 1 i.e., T(0,n)=1 and T(m,0)=1.

But, how do I derive the time complexity from the above recurrence relation?

• Please only post to one site at a time. Cross-posted here: math.stackexchange.com/questions/4678728 Apr 14, 2023 at 3:42
• The recurrence is symmetric in $n,m$, but the solution that you show is not. This cannot be.
– user16034
Apr 14, 2023 at 8:05

Hint:

A solution of the homogeneous recurrence is well-known to be

$$T(n,m)=\binom{n+m}n=\frac{(n+m)!}{n!\,m!}$$

by Pascal's identity.

And a particular solution of the non-homogeneous solution is simply

$$T(n,m)=-c.$$

• and 2^{m+n} is another homogeneous solution
– 1001
Apr 14, 2023 at 21:11
• @1001: that does not meet the limit conditions.
– user16034
Apr 15, 2023 at 9:48