Generic enums in Rust - Time & Space Complexity

Time Complexity: Generic enums

O(1)

Understanding Time Complexity

We want to understand how the time it takes to run code with generic enums changes as the input grows.

Specifically, how does using generic enums affect the number of steps the program takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

enum Container<T> {
    Single(T),
    Pair(T, T),
}

fn process(container: Container<i32>) {
    match container {
        Container::Single(value) => println!("Value: {}", value),
        Container::Pair(a, b) => println!("Sum: {}", a + b),
    }
}
    

This code defines a generic enum with one or two values and a function that processes it by matching the enum variants.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matching on enum variants and printing values.
• How many times: Exactly once per call, no loops or recursion.

How Execution Grows With Input

Since the function processes one enum value at a time without loops, the steps stay the same no matter the input size.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The work does not increase with input size because there is no loop or recursion.

Final Time Complexity

Time Complexity: O(1)

This means the time to run the code stays the same no matter how big the input is.

Common Mistake

[X] Wrong: "Using generics or enums always makes the code slower as input grows."

[OK] Correct: Here, the generic enum just holds values and the code runs a simple match once, so time does not grow with input size.

Interview Connect

Understanding how generic enums behave helps you explain how your code handles different data shapes efficiently, a useful skill in many coding tasks.

Self-Check

"What if the enum held a vector of values instead of one or two? How would the time complexity change?"

Practice

1. What is the main benefit of using generic enums in Rust?

easy

A. They allow enums to hold different types of data without rewriting code.

B. They make enums run faster by using less memory.

C. They automatically generate functions for enums.

D. They restrict enums to only one data type.

Solution

1. Step 1: Understand what generic enums do

   Generic enums let you define an enum that can hold different types of data by using type parameters.

2. Step 2: Identify the benefit

   This means you can reuse the same enum for many data types without rewriting it for each type.

3. Final Answer:

   They allow enums to hold different types of data without rewriting code. -> Option A

4. Quick Check:

   Generic enums = flexible data types [OK]

Hint: Generic enums = one enum, many data types [OK]

Common Mistakes:

• Thinking generic enums improve speed
• Believing they auto-generate functions
• Assuming they limit data types

2. Which of the following is the correct syntax to define a generic enum named Option with a type parameter T?

easy

A. enum Option<T> { Some(T), None }

B. enum Option { Some<T>(T), None }

C. enum Option<T> { Some, None(T) }

D. enum Option { Some(T), None }

Solution

1. Step 1: Recall generic enum syntax

   Generic enums declare the type parameter after the enum name, like enum Name<T>.

2. Step 2: Check variant definitions

   Variants can use the generic type T directly, e.g., Some(T). The None variant has no data.

3. Final Answer:

   enum Option<T> { Some(T), None } -> Option A

4. Quick Check:

   Generic param after enum name = enum Option<T> { Some(T), None } [OK]

Hint: Generic param goes after enum name, not variant [OK]

Common Mistakes:

• Putting <T> after variant name
• Adding data to None variant
• Omitting generic parameter after enum name

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

enum Result {
    Ok(T),
    Err(E),
}

fn main() {
    let value: Result = Result::Ok(10);
    match value {
        Result::Ok(v) => println!("Value: {}", v),
        Result::Err(e) => println!("Error: {}", e),
    }
}

medium

A. Compilation error

B. Error: 10

C. Value: Err

D. Value: 10

Solution

1. Step 1: Understand the enum and value

   The enum Result has two variants: Ok with type T and Err with type E. The variable value is Result::Ok(10).

2. Step 2: Match arms and output

   The match checks if value is Ok or Err. Since it is Ok(10), it prints Value: 10.

3. Final Answer:

   Value: 10 -> Option D

4. Quick Check:

   Match Ok(10) prints Value: 10 [OK]

Hint: Match enum variant to print correct value [OK]

Common Mistakes:

• Confusing Ok and Err variants
• Expecting error output for Ok variant
• Thinking code won't compile

4. Identify the error in this generic enum usage:

enum Wrapper<T> {
    Value(T),
}

fn main() {
    let w: Wrapper = Wrapper::Value(5);
}

medium

A. Cannot use Wrapper::Value to create a value.

B. Enum variants cannot hold generic types.

C. Missing type parameter <i32> when declaring w.

D. The enum must have a lifetime parameter.

Solution

1. Step 1: Check enum declaration and usage

   The enum Wrapper is generic over T. When creating w, the type parameter is missing.

2. Step 2: Understand Rust's type inference rules

   Rust requires specifying the type parameter explicitly or letting it infer from context. Here, w is declared without <i32>, so it causes an error.

3. Final Answer:

   Missing type parameter <i32> when declaring w. -> Option C

4. Quick Check:

   Generic enum needs type parameter specified [OK]

Hint: Always specify generic type when declaring variables [OK]

Common Mistakes:

• Omitting generic type parameter
• Thinking enum variants can't hold generics
• Adding unnecessary lifetime parameters

5. Given this generic enum:

enum Container<T> {
    Single(T),
    Multiple(Vec<T>),
}

Which code correctly creates a Container holding multiple String values and prints each string?

hard

A. let c: Container = Container::Multiple(vec!["a", "b"]);
match c {
Container::Multiple(v) => for s in v { println!("{}", s); },
_ => (),
}

B. let c = Container::Multiple(vec!["a".to_string(), "b".to_string()]);
if let Container::Multiple(v) = c {
for s in v { println!("{}", s); }
}

C. let c = Container::Single(vec!["a".to_string(), "b".to_string()]);
match c {
Container::Multiple(v) => for s in v { println!("{}", s); },
_ => (),
}

D. let c = Container::Multiple(vec!["a", "b"]);
if let Container::Multiple(v) = c {
for s in v { println!("{}", s); }
}

Solution

1. Step 1: Check type correctness in creation

   The enum Container expects Vec<T> for Multiple. Using vec!["a".to_string(), "b".to_string()] creates a Vec<String>, matching Container<String>.

2. Step 2: Verify pattern matching and printing

   The if let correctly matches Container::Multiple(v) and iterates over v to print each string.

3. Final Answer:

   Code correctly creates and prints the strings. -> Option B

4. Quick Check:

   Correct generic type and pattern matching = let c = Container::Multiple(vec!["a".to_string(), "b".to_string()]); if let Container::Multiple(v) = c { for s in v { println!("{}", s); } } [OK]

Hint: Use to_string() for String vectors and match variants properly [OK]

Common Mistakes:

• Missing generic type annotation
• Using wrong variant for multiple values
• Using string slices instead of String objects