While loop in C - Time & Space Complexity

Time Complexity: While loop

O(n)

Understanding Time Complexity

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

How does the number of steps increase when the loop runs more times?

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 that repeats until i reaches n, doing a small task each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Each time n gets bigger, the loop runs more times, adding more steps.

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

Pattern observation: The number of steps grows directly with n; if n doubles, steps double.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the size of n.

Common Mistake

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

[OK] Correct: The loop runs n times, so bigger n means more steps and more time.

Interview Connect

Understanding how loops grow with input helps you explain your code clearly and shows you know how programs scale.

Self-Check

"What if we changed the loop to increase i by 2 each time? How would the time complexity change?"