Edit Distance Problem Levenshtein in DSA Typescript - Time & Space Complexity

Time Complexity: Edit Distance Problem Levenshtein

O(m * n)

Understanding Time Complexity

We want to know how the time needed to find the edit distance between two words grows as the words get longer.

The question is: how does the number of steps change when the input words become bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function levenshteinDistance(a: string, b: string): number {
  const dp: number[][] = Array(a.length + 1).fill(null).map(() => Array(b.length + 1).fill(0));
  for (let i = 0; i <= a.length; i++) dp[i][0] = i;
  for (let j = 0; j <= b.length; j++) dp[0][j] = j;
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
      else dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
    }
  }
  return dp[a.length][b.length];
}
    

This code calculates the minimum number of edits needed to change one word into another using a grid to store results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops filling a 2D table of size (length of a + 1) by (length of b + 1).
• How many times: The inner loop runs for each character of the second word, and the outer loop runs for each character of the first word, so total steps multiply.

How Execution Grows With Input

As the words get longer, the number of steps grows by multiplying their lengths.

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

Pattern observation: Doubling the length roughly squares the number of steps needed.

Final Time Complexity

Time Complexity: O(m * n)

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

Common Mistake

[X] Wrong: "The algorithm only depends on the longer word's length, so it's O(n)."

[OK] Correct: The algorithm compares every character of the first word with every character of the second, so both lengths matter and multiply the work.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming solves problems efficiently by storing results and avoiding repeated work.

Self-Check

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