Loop execution flow in C++ - Time & Space Complexity

Time Complexity: Loop execution flow

O(n)

Understanding Time Complexity

When we look at loops in code, we want to know how many times the steps inside run as the input grows.

We ask: How does the work increase when the loop runs more times?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (int i = 0; i < n; i++) {
    // some simple operation
    sum += i;
}
    

This code runs a loop from 0 up to n-1 and adds each number to sum.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The addition inside the loop (sum += i)
• How many times: Exactly n times, once for each loop cycle

How Execution Grows With Input

As n grows, the number of additions grows the same way.

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

Pattern observation: The work grows directly in step with n. Double n, double the work.

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 loop runs faster because it just adds numbers, so time is constant."

[OK] Correct: Even simple steps add up when repeated many times. More loops mean more total work.

Interview Connect

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

Self-Check

"What if we added a nested loop inside this loop? How would the time complexity change?"