While loop in Rust - Time & Space Complexity

Time Complexity: While loop

O(n)

Understanding Time Complexity

We want to understand how the time a while loop takes changes as the input size grows.

Specifically, how many times does the loop run when the input gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn count_down(mut n: i32) {
    while n > 0 {
        println!("{}", n);
        n -= 1;
    }
}

This code counts down from n to 1, printing each number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that prints and decreases n.
• How many times: It runs once for each number from n down to 1, so n times.

How Execution Grows With Input

As n gets bigger, the loop runs more times, directly matching n.

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

Pattern observation: The number of operations grows in a straight line with n.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows directly in proportion to the input size n.

Common Mistake

[X] Wrong: "The while loop always takes the same time no matter what n is."

[OK] Correct: The loop runs once for each number from n down to 1, so bigger n means more loops and more time.

Interview Connect

Understanding how loops grow with input size helps you explain your code clearly and shows you know how to think about efficiency.

Self-Check

"What if we changed the loop to count down by 2 each time instead of 1? How would the time complexity change?"