Question

What is the time complexity of solving the Longest Common Subsequence problem using Dynamic Programming?

• A. O(n)
• B. O(n log n)
• C. O(log n)
• D. O(n²)

Hint:

The DP table has one cell per pair of index positions in the two strings, and each cell costs constant time.

Answer 1

The Correct Option is D

Step 1: The standard DP for Longest Common Subsequence builds a table indexed by positions in the two strings. Let the strings have lengths \( m \) and \( n \).

Step 2: The table has \( (m+1)(n+1) \) cells, and each cell is filled in constant time from a small number of neighbours. So the work is \( O(mn) \).

Step 3: When both strings have about the same length \( n \), this becomes \( O(n \cdot n) = O(n^2) \).

Step 4: Among the options the matching bound is \( O(n^2) \), option D.