Longest Common Subsequence in DSA Typescript - Time & Space Complexity

Time Complexity: Longest Common Subsequence

O(m x n)

Understanding Time Complexity

We want to understand how the time needed to find the longest common subsequence grows as the input strings get longer.

The question is: how does the work increase when the strings become bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function lcs(X: string, Y: string): number {
  const m = X.length, n = Y.length;
  const dp: number[][] = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (X[i - 1] === Y[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[m][n];
}
    

This code finds the length of the longest common subsequence between two strings using a table to store results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over both strings to fill the dp table.
• How many times: Outer loop runs m times, inner loop runs n times, so total m x n times.

How Execution Grows With Input

As the lengths of the two strings grow, the number of operations grows by multiplying their lengths.

Input Size (m, n)	Approx. Operations
10, 10	100
100, 100	10,000
1000, 1000	1,000,000

Pattern observation: Doubling the length of both strings roughly quadruples the work.

Final Time Complexity

Time Complexity: O(m x n)

This means the time needed grows proportionally to the product of the lengths of the two input strings.

Common Mistake

[X] Wrong: "The algorithm runs in linear time because it just loops through the strings once."

[OK] Correct: Actually, it uses nested loops, so it compares every character of one string with every character of the other, making the work multiply.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves efficiency and why nested loops matter in real problems.

Self-Check

"What if we used recursion without memoization? How would the time complexity change?"