Generic functions in Rust - Time & Space Complexity

Time Complexity: Generic functions

O(n)

Understanding Time Complexity

We want to see how the time a generic function takes changes as the input size grows.

How does using a generic type affect the speed when the function runs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn print_items(items: &[T]) {
    for item in items {
        println!("{}", item);
    }
}

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    print_items(&numbers);
}
    

This function prints each item in a list, using a generic type that can be any printable value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each item in the list.
• How many times: Once for every item in the input slice.

How Execution Grows With Input

As the list gets bigger, the function prints more items, so it takes longer.

Input Size (n)	Approx. Operations
10	10 print actions
100	100 print actions
1000	1000 print actions

Pattern observation: The time grows directly with the number of items; doubling items doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the number of items to print.

Common Mistake

[X] Wrong: "Using generics makes the function slower because it has to handle many types."

[OK] Correct: The generic function runs the same loop regardless of type; the time depends on input size, not the type itself.

Interview Connect

Understanding how generic functions behave helps you explain code efficiency clearly and confidently in real projects and interviews.

Self-Check

"What if we changed the function to print pairs of items instead of single items? How would the time complexity change?"

Practice

1. What does the <T> mean in a Rust function definition like fn example<T>(value: T) {}?

easy

A. It makes the function generic, so it can accept any type.

B. It defines a new variable inside the function.

C. It restricts the function to only work with integers.

D. It marks the function as unsafe.

Solution

1. Step 1: Understand the syntax <T> in Rust

   The <T> after the function name declares a generic type parameter named T.

2. Step 2: Explain the effect of generic type parameter

   This allows the function to accept any type for value, making it flexible and reusable.

3. Final Answer:

   It makes the function generic, so it can accept any type. -> Option A

4. Quick Check:

   Generic type parameter = flexible function input [OK]

Hint: Look for <T> after function name for generics [OK]

Common Mistakes:

• Thinking <T> is a variable declaration
• Assuming it restricts to one type like integer
• Confusing it with unsafe code marker

2. Which of the following is the correct syntax to define a generic function named print_value that takes one argument of any type T?

easy

A. fn print_value(T value) {}

B. fn print_value<T>(value: T) {}

C. fn print_value(value: <T>) {}

D. fn print_value(value: T<>) {}

Solution

1. Step 1: Recall generic function syntax in Rust

   Generic functions use <T> after the function name to declare the generic type.

2. Step 2: Match the syntax with options

   fn print_value<T>(value: T) {} correctly places <T> after the function name and uses value: T as parameter type.

3. Final Answer:

   fn print_value<T>(value: T) {} -> Option B

4. Quick Check:

   Generic syntax = fn name<T>(param: T) [OK]

Hint: Generic type always goes after function name in angle brackets [OK]

Common Mistakes:

• Putting T inside parameter parentheses incorrectly
• Using angle brackets around parameter type
• Missing angle brackets after function name

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

fn show_value<T: std::fmt::Display>(val: T) {
    println!("Value: {}", val);
}

fn main() {
    show_value(10);
    show_value("hello");
}

medium

A. Value: 10\nValue: hello

B. Value: 10\nValue: 10

C. Compilation error due to missing trait bound

D. Runtime error

Solution

1. Step 1: Understand the generic function with trait bound

   The function show_value requires T to implement Display so it can be printed.

2. Step 2: Check calls with integer and string

   Both 10 (integer) and "hello" (string) implement Display, so both calls print correctly.

3. Final Answer:

   Value: 10 Value: hello -> Option A

4. Quick Check:

   Trait bound allows printing = output shown [OK]

Hint: Check trait bounds to know if printing works [OK]

Common Mistakes:

• Assuming generic functions print without trait bounds
• Thinking string prints as number
• Expecting compilation error without trait bound

4. Identify the error in this generic function and how to fix it:

fn compare<T>(a: T, b: T) -> bool {
    a == b
}

medium

A. Function should return i32 instead of bool.

B. Function parameters should be references, not values.

C. Generic type T must be replaced with i32.

D. Missing trait bound T: PartialEq to use == operator.

Solution

1. Step 1: Understand use of == in generic function

   The == operator requires the type T to implement the PartialEq trait.

2. Step 2: Identify missing trait bound

   The function lacks T: PartialEq bound, so compiler will error when using ==.

3. Final Answer:

   Missing trait bound T: PartialEq to use == operator. -> Option D

4. Quick Check:

   Operator needs trait bound = add T: PartialEq [OK]

Hint: Add trait bounds when using operators on generics [OK]

Common Mistakes:

• Ignoring trait bounds for operators
• Changing return type unnecessarily
• Replacing generic with concrete type without reason

5. You want to write a generic function largest that returns the largest element from a slice of any type T. Which of these is the correct way to define it?

hard

A. fn largest<T>(list: &[T]) -> T { let mut largest = list[0]; for &item in list { if item > largest { largest = item; } } largest }

B. fn largest(list: &[i32]) -> i32 { let mut largest = list[0]; for &item in list { if item > largest { largest = item; } } largest }

C. fn largest<T: PartialOrd + Copy>(list: &[T]) -> T { let mut largest = *list[0]; for &item in list { if item > largest { largest = item; } } largest }

D. fn largest<T: PartialEq>(list: &[T]) -> T { list[0] }

Solution

1. Step 1: Identify required traits for comparison and copying

   To compare elements with >, T must implement PartialOrd. To copy elements, Copy trait is needed.

2. Step 2: Check function signature and body

   fn largest<T: PartialOrd + Copy>(list: &[T]) -> T { let mut largest = *list[0]; for &item in list { if item > largest { largest = item; } } largest } correctly adds T: PartialOrd + Copy and uses a loop to find the largest element.

3. Final Answer:

   fn largest<T: PartialOrd + Copy>(list: &[T]) -> T { ... } -> Option C

4. Quick Check:

   Traits PartialOrd + Copy needed for generic largest function [OK]

Hint: Add PartialOrd and Copy traits for generic comparisons [OK]

Common Mistakes:

• Omitting trait bounds causing compile errors
• Returning wrong type or missing copy trait
• Using concrete types instead of generics