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?"

Practice

1.

What does a while loop do in Rust?

easy

A. Stops the program immediately

B. Runs code only once

C. Repeats code a fixed number of times

D. Repeats code as long as a condition is true

Solution

1. Step 1: Understand the purpose of a while loop

   A while loop runs repeatedly while its condition is true.

2. Step 2: Compare options with this behavior

   Only Repeats code as long as a condition is true describes repeating code while a condition is true.

3. Final Answer:

   Repeats code as long as a condition is true -> Option D

4. Quick Check:

   while loop = repeat while true [OK]

Hint: While loops run while condition is true [OK]

Common Mistakes:

• Confusing while loop with for loop
• Thinking while loop runs fixed times
• Believing while loop runs once only

2.

Which of the following is the correct syntax for a while loop in Rust?

??? x < 5 {
    println!("{}", x);
    x += 1;
}

easy

A. while

B. loop

C. for

D. if

Solution

1. Step 1: Identify the keyword for a while loop

   The keyword to start a while loop is while.

2. Step 2: Check other keywords

   loop is an infinite loop, for is for fixed iteration, if is conditional, not looping.

3. Final Answer:

   while -> Option A

4. Quick Check:

   while keyword starts while loop [OK]

Hint: While loops start with 'while' keyword [OK]

Common Mistakes:

• Using 'loop' instead of 'while'
• Using 'for' for while loops
• Using 'if' instead of loop keyword

3.

What will be the output of this Rust code?

let mut count = 1;
while count <= 3 {
    println!("{}", count);
    count += 1;
}

medium

A. No output

B. 1 2 3 4

C. 1 2 3

D. 0 1 2

Solution

1. Step 1: Analyze the loop condition and variable

   The loop runs while count is less than or equal to 3, starting at 1.

2. Step 2: Trace the output values

   It prints 1, then 2, then 3, then stops because count becomes 4.

3. Final Answer:

   1 2 3 -> Option C

4. Quick Check:

   Prints 1 to 3 inclusive [OK]

Hint: Count from 1 to 3 prints 1 2 3 [OK]

Common Mistakes:

• Thinking it prints 4
• Starting count at 0
• Assuming no output

4.

Find the error in this Rust code using a while loop:

let mut i = 0;
while i < 5 {
    println!("{}", i);
}

medium

A. Wrong comparison operator in while condition

B. Missing increment of 'i' inside the loop

C. 'i' should be immutable, not mutable

D. println! macro syntax is incorrect

Solution

1. Step 1: Check loop variable update

   The variable 'i' is never increased inside the loop, so the condition never becomes false.

2. Step 2: Understand effect of missing increment

   Without increment, the loop runs forever (infinite loop).

3. Final Answer:

   Missing increment of 'i' inside the loop -> Option B

4. Quick Check:

   Increment needed to avoid infinite loop [OK]

Hint: Always update loop variable inside while loop [OK]

Common Mistakes:

• Forgetting to increment loop variable
• Using wrong operator but code still compiles
• Misunderstanding mutability requirement

5.

Write a while loop in Rust that prints all even numbers from 2 to 10 inclusive.

Which code snippet correctly does this?

???

hard

A. let mut n = 2;
while n <= 10 {
println!("{}", n);
n += 2;
}

B. let mut n = 1;
while n < 10 {
if n % 2 == 0 {
println!("{}", n);
}
n += 1;
}

C. let mut n = 2;
while n < 10 {
println!("{}", n);
n += 2;
}

D. let mut n = 0;
while n <= 10 {
println!("{}", n);
n += 2;
}

Solution

1. Step 1: Check the range and values printed

   We want even numbers from 2 to 10 inclusive, so start at 2 and go up to 10.

2. Step 2: Analyze each option

   let mut n = 2; while n <= 10 { println!("{}", n); n += 2; } starts at 2, increments by 2, and stops at 10 inclusive. let mut n = 1; while n < 10 { if n % 2 == 0 { println!("{}", n); } n += 1; } starts at 1 and checks evenness each time but stops before 10, missing 10. let mut n = 2; while n < 10 { println!("{}", n); n += 2; } stops before 10, missing 10. let mut n = 0; while n <= 10 { println!("{}", n); n += 2; } starts at 0, which is even but outside the requested range.

3. Final Answer:

   let mut n = 2; while n <= 10 { println!("{}", n); n += 2; } -> Option A

4. Quick Check:

   Start 2, step 2, end 10 inclusive [OK]

Hint: Start at 2, add 2 each loop until 10 [OK]

Common Mistakes:

• Starting at 0 instead of 2
• Stopping before 10
• Not incrementing by 2