Recursive pattern matching in C Sharp (C#) - Time & Space Complexity

Time Complexity: Recursive pattern matching

O(2^(m+n))

Understanding Time Complexity

When we use recursive pattern matching, the program calls itself to check parts of data step by step.

We want to know how the time it takes grows as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool MatchPattern(string text, string pattern) {
    return (text, pattern) switch {
        ("", "") => true,
        (_, "") => false,
        (string t, string p) when p[0] == '*' =>
            MatchPattern(t, p[1..]) || (t != "" && MatchPattern(t[1..], p)),
        (string t, string p) when p[0] == '?' =>
            t != "" && MatchPattern(t[1..], p[1..]),
        (string t, string p) =>
            t != "" && t[0] == p[0] && MatchPattern(t[1..], p[1..])
    };
}
    

This code checks if a text matches a pattern with wildcards using recursion and pattern matching.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls that reduce the text or pattern by one character.
• How many times: Up to the length of the text and pattern combined, but can branch due to '*'.

How Execution Grows With Input

Each recursive call tries to match smaller parts of the text and pattern, sometimes branching into two calls when '*' is found.

Input Size (n)	Approx. Operations
10	Up to about 2^10 (around 1000) calls in worst case
100	Up to about 2^100 calls (very large, impractical)
1000	Exponential growth, too large to compute

Pattern observation: The number of operations can grow very fast, doubling with each '*' in the pattern.

Final Time Complexity

Time Complexity: O(2^(m+n))

This means the time can grow exponentially with the combined length of text (m) and pattern (n), especially due to branching on '*'.

Common Mistake

[X] Wrong: "The recursion will always run in linear time because it reduces the input each call."

[OK] Correct: Sometimes the recursion splits into two calls (branching), causing the total calls to grow exponentially, not just linearly.

Interview Connect

Understanding recursive pattern matching helps you think about how recursion and branching affect performance, a key skill in many coding problems.

Self-Check

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