Implementing traits in Rust - Time & Space Complexity

Time Complexity: Implementing traits

O(n)

Understanding Time Complexity

When we implement traits in Rust, we add behavior to types. It's important to see how the time it takes to run these behaviors changes as input grows.

We want to know: how does the running time grow when we call trait methods on data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

trait Summable {
    fn sum(&self) -> i32;
}

struct Numbers {
    values: Vec<i32>,
}

impl Summable for Numbers {
    fn sum(&self) -> i32 {
        let mut total = 0;
        for &num in &self.values {
            total += num;
        }
        total
    }
}

This code defines a trait with a sum method and implements it for a struct holding a list of numbers. The sum method adds all numbers in the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each number in the vector to add it.
• How many times: Once for every element in the vector.

How Execution Grows With Input

As the list of numbers gets bigger, the time to add them grows too.

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

Pattern observation: The time grows directly with the number of items. Double the items, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the sum method grows in a straight line with the size of the list.

Common Mistake

[X] Wrong: "Implementing a trait method like sum always runs instantly, no matter the list size."

[OK] Correct: The method actually loops through all items, so bigger lists take more time.

Interview Connect

Understanding how trait methods run helps you explain your code's efficiency clearly. It shows you know how behavior affects performance as data grows.

Self-Check

"What if the sum method used recursion instead of a loop? How would the time complexity change?"