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?"

Practice

1.

What does a for loop in C++ do?

easy

A. Defines a new function

B. Runs code only once

C. Stops the program immediately

D. Repeats a block of code a fixed number of times

Solution

1. Step 1: Understand the purpose of a for loop

   A for loop is designed to repeat code multiple times based on a condition.

2. Step 2: Identify the correct description

   Among the options, only repeating code a fixed number of times matches the for loop's behavior.

3. Final Answer:

   Repeats a block of code a fixed number of times -> Option D

4. Quick Check:

   For loop = repeat fixed times [OK]

Hint: For loops repeat code a set number of times [OK]

Common Mistakes:

• Thinking for loops run only once
• Confusing for loops with if statements
• Believing for loops stop the program

2.

Which of the following is the correct syntax for a for loop in C++?

for (___; i < 5; i++) {
    // code
}

easy

A. int i = 0

B. i = 0

C. int i

D. int i == 0

Solution

1. Step 1: Check initialization syntax in for loop

   The initialization part must declare and initialize the loop variable, e.g., int i = 0.

2. Step 2: Compare options for correctness

   Only int i = 0 correctly declares and initializes the variable.

3. Final Answer:

   int i = 0 -> Option A

4. Quick Check:

   Initialization needs declaration and assignment [OK]

Hint: Initialization needs declaration and assignment [OK]

Common Mistakes:

• Using 'int i' without initialization
• Using 'int i == 0' which is a comparison
• Omitting the type declaration

3.

What is the output of this code?

for (int i = 1; i <= 3; i++) {
    std::cout << i * 2 << " ";
}

medium

A. 1 2 3

B. 2 4 6

C. 0 2 4

D. 2 3 4

Solution

1. Step 1: Identify loop iterations

   The loop runs with i = 1, 2, 3 because condition is i <= 3.

2. Step 2: Calculate output for each iteration

   Outputs are i*2: 2, 4, 6 printed with spaces.

3. Final Answer:

   2 4 6 -> Option B

4. Quick Check:

   Multiply i by 2 each loop [OK]

Hint: Multiply loop variable by 2 each iteration [OK]

Common Mistakes:

• Confusing loop range (off by one)
• Printing i instead of i*2
• Missing spaces in output

4.

Find the error in this for loop:

for (int i = 0; i > 5; i++) {
    std::cout << i << " ";
}

medium

A. Variable i is not declared

B. Missing semicolon after i++

C. The condition 'i > 5' is incorrect, loop never runs

D. The loop will run infinitely

Solution

1. Step 1: Analyze the loop condition

   The condition is i > 5 but i starts at 0, so it is false immediately.

2. Step 2: Understand loop execution

   Since condition is false at start, loop body never executes.

3. Final Answer:

   The condition 'i > 5' is incorrect, loop never runs -> Option C

4. Quick Check:

   Condition false at start means no loop runs [OK]

Hint: Check if loop condition is true initially [OK]

Common Mistakes:

• Assuming loop runs despite false condition
• Thinking missing semicolon causes error here
• Confusing variable declaration errors

5.

How can you use a for loop to print all even numbers from 2 to 10 inclusive?

Choose the correct code snippet:

hard

A. for (int i = 2; i <= 10; i += 2) { std::cout << i << ' '; }

B. for (int i = 1; i < 10; i++) { if (i % 2 == 0) std::cout << i << ' '; }

C. for (int i = 2; i < 10; i++) { std::cout << i * 2 << ' '; }

D. for (int i = 0; i <= 10; i += 3) { std::cout << i << ' '; }

Solution

1. Step 1: Understand the goal

   We want to print even numbers 2,4,6,8,10 inclusive.

2. Step 2: Check each option

   for (int i = 2; i <= 10; i += 2) { std::cout << i << ' '; } increments by 2 starting at 2, printing 2,4,6,8,10 correctly.
   for (int i = 1; i < 10; i++) { if (i % 2 == 0) std::cout << i << ' '; } prints 2,4,6,8 but misses 10.
   for (int i = 2; i < 10; i++) { std::cout << i * 2 << ' '; } prints 4,6,8,10,12,14,16,18 (wrong range).
   for (int i = 0; i <= 10; i += 3) { std::cout << i << ' '; } increments by 3, not even numbers.

3. Final Answer:

   for (int i = 2; i <= 10; i += 2) { std::cout << i << ' '; } -> Option A

4. Quick Check:

   Increment by 2 from 2 to 10 [OK]

Hint: Increment loop variable by 2 starting at 2 [OK]

Common Mistakes:

• Using wrong increment step
• Forgetting to include 10
• Using condition inside loop unnecessarily