Integer types in Rust - Time & Space Complexity

Time Complexity: Integer types

O(n)

Understanding Time Complexity

When working with integer types in Rust, it's helpful to know how operations on them affect program speed.

We want to see how the time to run code changes as the numbers get bigger or smaller.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each integer to the sum inside a loop.
• How many times: Once for every number in the list.

How Execution Grows With Input

As the list gets longer, the number of additions grows at the same rate.

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

Pattern observation: Doubling the list size doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to add numbers grows directly with how many numbers there are.

Common Mistake

[X] Wrong: "Adding integers is always instant, so time doesn't grow with input size."

[OK] Correct: While each addition is fast, doing many additions one after another takes more time as the list grows.

Interview Connect

Understanding how simple operations like adding integers scale helps you explain program speed clearly and confidently.

Self-Check

"What if we changed the list to a nested list of integers? How would the time complexity change?"