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

Time Complexity: Edit Distance Problem Levenshtein

O(3^{min(m,n)})

Understanding Time Complexity

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

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.

int min(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int editDistance(char *s1, char *s2, int m, int n) {
    if (m == 0) return n;
    if (n == 0) return m;

    if (s1[m - 1] == s2[n - 1])
        return editDistance(s1, s2, m - 1, n - 1);

    return 1 + min(
        editDistance(s1, s2, m, n - 1),    // Insert
        editDistance(s1, s2, m - 1, n),    // Remove
        editDistance(s1, s2, m - 1, n - 1) // Replace
    );
}
    

This code finds the minimum number of edits (insert, remove, replace) to change one string into another using recursion.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls that explore all combinations of substring lengths.
• How many times: Each call branches into three more calls unless base case is reached, leading to many repeated calls.

How Execution Grows With Input

Each character in the first word can match with each character in the second word, and the recursion tries all possibilities.

Input Size (m, n)	Approx. Operations
5, 5	Hundreds of calls
10, 10	Thousands of calls
20, 20	Millions of calls

Pattern observation: The number of calls grows very fast, roughly tripling with each increase in input size.

Final Time Complexity

Time Complexity: O(3^{min(m,n)})

This means the time needed grows very fast as the lengths of the two strings increase, because the recursion explores many overlapping cases.

Common Mistake

[X] Wrong: "The recursive solution runs quickly because it only checks each character once."

[OK] Correct: The recursion repeats many calls for the same substrings, causing exponential growth in steps.

Interview Connect

Understanding this complexity helps you explain why a simple recursive solution is slow and why dynamic programming is needed to improve it.

Self-Check

"What if we add memoization to store results of subproblems? How would the time complexity change?"