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?"

Practice

1. What is the main purpose of the match statement in Rust?

easy

A. To check a value against multiple patterns clearly and concisely

B. To create loops that run a fixed number of times

C. To define new data types

D. To handle errors using exceptions

Solution

1. Step 1: Understand the role of match

   The match statement compares a value against many patterns, making code clearer than many if-else statements.

2. Step 2: Compare with other options

   Loops run repeatedly, data types define structures, and exceptions handle errors, but match is for pattern matching.

3. Final Answer:

   To check a value against multiple patterns clearly and concisely -> Option A

4. Quick Check:

   Match = pattern checking [OK]

Hint: Match replaces many if-else with clear pattern checks [OK]

Common Mistakes:

• Confusing match with loops
• Thinking match defines types
• Assuming match handles exceptions

2. Which of the following is the correct syntax for a match expression in Rust?

easy

A. match value { pattern1 => expr1, pattern2 => expr2, _ => default_expr }

B. match (value) { pattern1: expr1; pattern2: expr2; default: default_expr }

C. match value { pattern1 -> expr1, pattern2 -> expr2, _ -> default_expr }

D. match value { pattern1 => expr1; pattern2 => expr2; _ => default_expr }

Solution

1. Step 1: Recall Rust match syntax

   Rust uses curly braces with patterns followed by => and expressions separated by commas.

2. Step 2: Check each option

   match value { pattern1 => expr1, pattern2 => expr2, _ => default_expr } uses correct braces, arrows, and commas. Options B and D use semicolons incorrectly. match value { pattern1 -> expr1, pattern2 -> expr2, _ -> default_expr } uses -> instead of =>.

3. Final Answer:

   match value { pattern1 => expr1, pattern2 => expr2, _ => default_expr } -> Option A

4. Quick Check:

   Correct match syntax uses => and commas [OK]

Hint: Use => between pattern and expression, separate arms with commas [OK]

Common Mistakes:

• Using semicolons instead of commas
• Using -> instead of =>
• Missing the catch-all _ pattern

3. What will be the output of this Rust code?

let number = 3;
match number {
    1 => println!("One"),
    2 => println!("Two"),
    3 => println!("Three"),
    _ => println!("Other"),
}

medium

A. One

B. Two

C. Other

D. Three

Solution

1. Step 1: Identify the matched value

   The variable number is 3, so the match will look for pattern 3.

2. Step 2: Find the matching arm

   The arm 3 => println!("Three") matches and prints "Three".

3. Final Answer:

   Three -> Option D

4. Quick Check:

   number=3 matches 3 => "Three" [OK]

Hint: Match value exactly to print correct output [OK]

Common Mistakes:

• Choosing default _ arm instead of exact match
• Confusing numbers with strings
• Ignoring the value of number

4. Identify the error in this Rust match code snippet:

let x = 5;
match x {
    1 => println!("One"),
    2 => println!("Two"),
    3 => println!("Three")
}

medium

A. Missing semicolon after println! macros

B. Using parentheses instead of curly braces in match

C. Missing catch-all _ pattern to handle other values

D. Incorrect variable declaration

Solution

1. Step 1: Check match arms completeness

   The match covers 1, 2, and 3 but does not handle other values like 5.

2. Step 2: Understand Rust match requirements

   Rust requires all possible values to be covered, usually by a catch-all _ pattern.

3. Final Answer:

   Missing catch-all _ pattern to handle other values -> Option C

4. Quick Check:

   Always include _ to cover unmatched cases [OK]

Hint: Always add _ arm to handle unexpected values [OK]

Common Mistakes:

• Forgetting the catch-all _ pattern
• Thinking semicolons are mandatory after println!
• Confusing braces with parentheses

5. Given this Rust code, what will be the output?

let grade = 'B';
match grade {
    'A' | 'B' | 'C' => println!("Pass"),
    'D' => println!("Conditional Pass"),
    _ => println!("Fail"),
}

hard

A. Conditional Pass

B. Pass

C. Fail

D. Compilation error

Solution

1. Step 1: Identify the value and patterns

   The variable grade is 'B'. The first arm matches 'A', 'B', or 'C'.

2. Step 2: Determine which arm runs

   Since 'B' matches the first arm, it prints "Pass".

3. Final Answer:

   Pass -> Option B

4. Quick Check:

   Multiple patterns with | match 'B' => "Pass" [OK]

Hint: Use | to match multiple patterns in one arm [OK]

Common Mistakes:

• Assuming only single pattern per arm
• Choosing wrong output for 'B'
• Thinking code causes compilation error