Generics with traits in Rust - Time & Space Complexity

Time Complexity: Generics with traits

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run code with generics and traits changes as the input grows.

Specifically, how does using traits with generics affect the number of steps the program takes?

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 code prints each item in a list using a generic function constrained by a trait.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the list gets bigger, the number of print steps grows in the same way.

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

Pattern observation: The work grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Using traits with generics makes the code slower and more complex in time."

[OK] Correct: The trait constraint only affects what types can be used, not how many times the code runs. The loop still runs once per item, so time grows the same way.

Interview Connect

Understanding how generics and traits affect time helps you explain your code clearly and shows you know how Rust handles flexible types efficiently.

Self-Check

What if the function also called another function inside the loop that itself loops over the items? How would the time complexity change?