For loop in C++ - Time & Space Complexity

Time Complexity: For loop

O(n)

Understanding Time Complexity

We want to understand how the time a for loop takes changes as we increase the number of times it runs.

How does the work grow 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++) {
    // simple operation
    sum += i;
}
    

This code adds numbers from 0 up to n-1 to a sum using a for loop.

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 with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in a straight line with the number of loop cycles.

Common Mistake

[X] Wrong: "The loop runs fast enough that its time doesn't depend on n."

[OK] Correct: Even if each step is quick, doing more steps still takes more time overall.

Interview Connect

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

Self-Check

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