What is the asymptotic time complexity of finding the Longest Common Subsequence of two strings of length m and n using dynamic programming?
Show answer
O(mn)
The LCS problem utilizes a 2D table to store the lengths of common subsequences for all possible prefixes. Building this table requires filling m * n cells, each taking constant time.
Also asked as:
- Using dynamic programming, what is the Big O time complexity to find the Longest Common Subsequence for strings of length m and n?