0
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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