Generic structs in Rust - Time & Space Complexity

Time Complexity: Generic structs

O(1)

Understanding Time Complexity

Let's see how the time it takes to run code with generic structs changes as we use more data.

We want to know how the program's work grows when the input size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Container<T> {
    items: Vec<T>,
}

impl<T> Container<T> {
    fn count_items(&self) -> usize {
        self.items.len()
    }
}

This code defines a generic struct holding a list of items and a method to count them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing the length of the vector.
• How many times: The length is retrieved once without looping.

How Execution Grows With Input

Explain the growth pattern intuitively.

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

Pattern observation: The operation count stays the same no matter how many items are in the container.

Final Time Complexity

Time Complexity: O(1)

This means the time to count items does not grow with more items; it stays constant.

Common Mistake

[X] Wrong: "Counting items in a generic struct always takes longer if there are more items."

[OK] Correct: The length method just returns a stored number, so it takes the same time no matter the size.

Interview Connect

Understanding how generic structs work with time helps you explain your code clearly and shows you know how data size affects speed.

Self-Check

"What if the count_items method instead summed a value from each item? How would the time complexity change?"