Do–while loop in C++ - Time & Space Complexity

Time Complexity: Do-while loop

O(n)

Understanding Time Complexity

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

Specifically, how many times the loop runs affects the total work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code runs a loop that repeats until the variable i reaches n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The do-while loop body runs repeatedly.
• How many times: It runs exactly n times, increasing i each time.

How Execution Grows With Input

As n grows, the loop runs more times, so the total work grows in a straight line with n.

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

Pattern observation: The work grows evenly as n increases.

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 do-while loop always runs at least once, so it takes constant time."

[OK] Correct: The loop runs once or more, but the total number of runs depends on n, so time grows with input size, not constant.

Interview Connect

Understanding how loops like do-while scale helps you explain how programs behave with bigger inputs, a key skill in coding interviews.

Self-Check

"What if the loop increments i by 2 each time instead of 1? How would the time complexity change?"