Match expression deep dive in Rust - Time & Space Complexity

Time Complexity: Match expression deep dive

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a match expression changes as the number of patterns grows.

How does adding more match arms affect the work the program does?

Scenario Under Consideration

Analyze the time complexity of the following Rust match expression.

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

This code matches a number to a string description using several patterns.

Identify Repeating Operations

Look for repeated checks or comparisons inside the match.

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

How Execution Grows With Input

As the number of match arms increases, the program may check more patterns before finding a match.

Input Size (number of arms)	Approx. Comparisons
3	Up to 3 comparisons
10	Up to 10 comparisons
100	Up to 100 comparisons

Pattern observation: The number of comparisons grows roughly in a straight line with the number of arms.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a match grows linearly with the number of patterns.

Common Mistake

[X] Wrong: "Match expressions always run in constant time no matter how many arms there are."

[OK] Correct: The program may need to check each arm one by one until it finds a match, so more arms usually mean more work.

Interview Connect

Understanding how match expressions scale helps you explain how your code behaves with more cases, showing you think about efficiency clearly.

Self-Check

"What if the match arms were arranged to check the most common cases first? How would that affect the time complexity in practice?"