Match overview in Rust - Time & Space Complexity

Time Complexity: Match overview

O(n)

Understanding Time Complexity

We want to understand how the time a Rust match statement takes changes as the number of patterns grows.

Specifically, how does checking many cases affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn describe_number(num: i32) -> &'static str {
    match num {
        1 => "one",
        2 => "two",
        3 => "three",
        4 => "four",
        5 => "five",
        _ => "other",
    }
}
    

This code matches a number against several fixed cases and returns a word for it or "other" if no match.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each pattern in the match until one fits.
• How many times: Up to the number of patterns (here 6 including the catch-all).

How Execution Grows With Input

As the number of patterns increases, the time to find a match grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The work grows directly with the number of patterns to check.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a match grows linearly as you add more patterns.

Common Mistake

[X] Wrong: "A match always runs in constant time no matter how many patterns there are."

[OK] Correct: The match checks patterns one by one until it finds a match, so more patterns usually mean more checks.

Interview Connect

Understanding how pattern matching scales helps you reason about code efficiency and choose better structures when needed.

Self-Check

"What if the match patterns were replaced by a hash map lookup? How would the time complexity change?"