What is Rust - Complexity Analysis

Time Complexity: What is Rust

O(n)

Understanding Time Complexity

When learning about Rust, it's helpful to understand how the time a program takes can grow as it works with more data.

We want to see how Rust code's speed changes when the input size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn sum_numbers(numbers: &[i32]) -> i32 {
    let mut total = 0;
    for &num in numbers.iter() {
        total += num;
    }
    total
}

This code adds up all the numbers in a list and returns the total.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each number in the list once.
• How many times: Exactly once for each number in the input list.

How Execution Grows With Input

As the list gets bigger, the time to add all numbers grows in a straight line.

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

Pattern observation: Doubling the input doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time grows directly with the size of the input list.

Common Mistake

[X] Wrong: "The time to add numbers stays the same no matter how many numbers there are."

[OK] Correct: Each number must be added, so more numbers mean more work and more time.

Interview Connect

Understanding how Rust code runs as input grows helps you explain your thinking clearly and shows you know how to write efficient programs.

Self-Check

"What if we changed the code to add numbers only if they are even? How would the time complexity change?"