Matching multiple patterns in Rust - Time & Space Complexity

Time Complexity: Matching multiple patterns

O(n)

Understanding Time Complexity

When we match multiple patterns in Rust, we want to know how long it takes as the input changes.

We ask: How does the time grow when we check many patterns?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn check_number(num: i32) {
    match num {
        1 | 2 | 3 => println!("Small number"),
        4 | 5 | 6 => println!("Medium number"),
        _ => println!("Other number"),
    }
}
    

This code checks if a number matches any of several patterns grouped with | (or).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the input against each pattern in order.
• How many times: Up to the number of patterns until a match is found.

How Execution Grows With Input

As the number of patterns grows, the checks grow too, but only until a match is found.

Input Size (patterns)	Approx. Operations
3	Up to 3 checks
10	Up to 10 checks
100	Up to 100 checks

Pattern observation: The number of checks grows linearly with the number of patterns.

Final Time Complexity

Time Complexity: O(n)

This means the time to match grows in a straight line as you add more patterns.

Common Mistake

[X] Wrong: "Matching multiple patterns happens all at once, so time stays the same no matter how many patterns."

[OK] Correct: Rust checks patterns one by one until it finds a match, so more patterns mean more checks in the worst case.

Interview Connect

Understanding how pattern matching time grows helps you write clear and efficient code, a skill valued in many coding challenges and real projects.

Self-Check

"What if we changed the patterns to use ranges instead of individual values? How would the time complexity change?"