While loop in C++ - Time & Space Complexity

Time Complexity: While loop

O(n)

Understanding Time Complexity

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

Specifically, how many times does the loop run as input grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int i = 0;
while (i < n) {
    // some constant time work
    i++;
}
    

This code runs a loop from 0 up to n-1, doing a small task each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs repeatedly.
• How many times: It runs once for each number from 0 up to n-1, so n times.

How Execution Grows With Input

As n gets bigger, the loop runs more times, growing in a straight line with n.

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

Pattern observation: If you double n, the work roughly doubles too.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The while loop runs forever or a fixed number of times regardless of n."

[OK] Correct: The loop clearly depends on n and runs exactly n times, so the time changes with input size.

Interview Connect

Understanding how loops grow with input is a key skill that helps you explain code efficiency clearly and confidently.

Self-Check

"What if we changed the increment from i++ to i += 2? How would the time complexity change?"