Do-while loop execution model in PHP - Time & Space Complexity

Time Complexity: Do-while loop execution model

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 does the loop run when the input gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    $i = 0;
    do {
        echo $i . "\n";
        $i++;
    } while ($i < $n);
    

This code prints numbers from 0 up to one less than n using a do-while loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The do-while loop that prints and increments the counter.
• How many times: It runs exactly n times, once for each number from 0 to n-1.

How Execution Grows With Input

As n grows, the number of loop runs grows the same way.

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

Pattern observation: The number of operations grows directly with n, so doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows in a straight line with the input size.

Common Mistake

[X] Wrong: "The do-while loop runs one more time than n because it checks after the first run."

[OK] Correct: The do-while loop runs exactly n times here, not more or less, because the condition is checked after each iteration and the loop stops when $i is no longer less than n.

Interview Connect

Understanding how loops like do-while behave helps you explain how your code scales and shows you can think about performance clearly.

Self-Check

"What if we changed the loop to run while $i <= $n instead of $i < $n? How would the time complexity change?"