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

Practice

1. What does the match expression do in Rust?

easy

A. It loops over a range of numbers.

B. It creates a new variable with a fixed value.

C. It defines a function with multiple parameters.

D. It compares a value against multiple patterns and executes matching code.

Solution

1. Step 1: Understand the purpose of match

   The match expression is used to compare a value against several patterns.

2. Step 2: Identify what happens on a match

   When a pattern matches, the corresponding code block runs, making match a clear way to handle multiple cases.

3. Final Answer:

   It compares a value against multiple patterns and executes matching code. -> Option D

4. Quick Check:

   Match expression = pattern matching [OK]

Hint: Match compares values to patterns and runs matching code [OK]

Common Mistakes:

• Thinking match creates variables
• Confusing match with loops
• Assuming match defines functions

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

easy

A. match value { 1 => println!("One") else println!("Other") }

B. match value { 1 => println!("One"), _ => println!("Other") }

C. match value { 1 -> println!("One"), _ -> println!("Other") }

D. match (value) { 1: println!("One"), _ : println!("Other") }

Solution

1. Step 1: Recall Rust match syntax

   Rust uses curly braces with patterns followed by => and the code to run.

2. Step 2: Check each option

   match value { 1 => println!("One"), _ => println!("Other") } uses correct syntax with => and a default case using _; others use invalid symbols like : or -> or else.

3. Final Answer:

   match value { 1 => println!("One"), _ => println!("Other") } -> Option B

4. Quick Check:

   Correct match syntax uses => and _ for default [OK]

Hint: Use => for patterns and _ for default case in match [OK]

Common Mistakes:

• Using : or -> instead of =>
• Omitting commas between arms
• Using else instead of _ for default

3. What is the output of this Rust code?

let x = Some(5);
match x {
  Some(n) if n > 3 => println!("Greater than 3: {}", n),
  Some(n) => println!("Less or equal to 3: {}", n),
  None => println!("No value"),
}

medium

A. Greater than 3: 5

B. Less or equal to 3: 5

C. No value

D. Compilation error

Solution

1. Step 1: Analyze the match arms and value

   The value is Some(5). The first arm matches Some(n) with a guard n > 3.

2. Step 2: Check the guard condition

   Since 5 > 3 is true, the first arm runs and prints "Greater than 3: 5".

3. Final Answer:

   Greater than 3: 5 -> Option A

4. Quick Check:

   Guard true triggers first arm output [OK]

Hint: Check if guards are true to pick correct match arm [OK]

Common Mistakes:

• Ignoring the if guard condition
• Choosing second arm without checking guard
• Thinking None matches Some value

4. Identify the error in this Rust match expression:

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

medium

A. Match arms must be in parentheses, not braces.

B. Using _ as default case is invalid.

C. Missing comma after the second arm (2 => ...).

D. Cannot match integer values directly.

Solution

1. Step 1: Check syntax of each match arm

   Each arm must end with a comma except possibly the last. The second arm lacks a comma after println!("Two").

2. Step 2: Validate other parts

   Using _ is valid for default, braces are correct, and matching integers is allowed.

3. Final Answer:

   Missing comma after the second arm (2 => ...). -> Option C

4. Quick Check:

   Commas separate match arms [OK]

Hint: Check commas after each match arm carefully [OK]

Common Mistakes:

• Forgetting commas between arms
• Misunderstanding _ as invalid
• Confusing braces with parentheses

5. Given a list of Option<i32> values, how can you use a match expression inside a loop to print only the positive numbers, ignoring None and non-positive values? Choose the correct code snippet.

hard

A. for val in list {
match val {
Some(n) if n > 0 => println!("Positive: {}", n),
_ => (),
}
}

B. for val in list {
match val {
Some(n) => println!("Positive: {}", n),
None => println!("No value"),
}
}

C. for val in list {
if let Some(n) = val {
if n > 0 {
println!("Positive: {}", n);
}
}
}

D. for val in list {
match val {
Some(n) if n <= 0 => println!("Positive: {}", n),
_ => (),
}
}

Solution

1. Step 1: Understand the requirement

   We want to print only positive numbers inside Some, ignoring None and non-positive.

2. Step 2: Analyze each option

   for val in list { match val { Some(n) if n > 0 => println!("Positive: {}", n), _ => (), } } matches Some(n) with guard n > 0 and prints; others ignore with _ => (). for val in list { match val { Some(n) => println!("Positive: {}", n), None => println!("No value"), } } prints all Some values regardless of positivity. for val in list { if let Some(n) = val { if n > 0 { println!("Positive: {}", n); } } } uses if let but is not a match expression. for val in list { match val { Some(n) if n <= 0 => println!("Positive: {}", n), _ => (), } } prints non-positive numbers, opposite of requirement.

3. Final Answer:

   for val in list { match val { Some(n) if n > 0 => println!("Positive: {}", n), _ => (), } } -> Option A

4. Quick Check:

   Match with guard filters positive Some values [OK]

Hint: Use if guards in match to filter values [OK]

Common Mistakes:

• Printing all Some values without checking positivity
• Using if let instead of match when asked
• Reversing guard condition