Program structure in Rust - Time & Space Complexity

Time Complexity: Program structure in Rust

O(n)

Understanding Time Complexity

When we look at how a Rust program is built, we want to know how the time it takes to run changes as the program grows.

We ask: How does the program's structure affect how long it runs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn main() {
    let numbers = vec![1, 2, 3, 4, 5];
    for num in &numbers {
        println!("Number: {}", num);
    }
}

This code creates a list of numbers and prints each one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list to print each number.
• How many times: Once for each number in the list.

How Execution Grows With Input

As the list gets bigger, the program prints more numbers, so it takes more time.

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

Pattern observation: The time 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: "The program runs in the same time no matter how many numbers there are."

[OK] Correct: Because the program prints each number, more numbers mean more work and more time.

Interview Connect

Understanding how loops affect time helps you explain how your code will behave as data grows, a key skill in programming.

Self-Check

"What if we added another loop inside the first one to print pairs of numbers? How would the time complexity change?"