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

Practice

1. What is the main purpose of a loop in C++ programming?

easy

A. To repeat a block of code multiple times

B. To store multiple values in a variable

C. To create a new data type

D. To stop the program execution immediately

Solution

1. Step 1: Understand the role of loops

   Loops are used to repeat a set of instructions multiple times without writing the code again and again.

2. Step 2: Identify the correct purpose

   Among the options, only repeating code matches the loop's purpose.

3. Final Answer:

   To repeat a block of code multiple times -> Option A

4. Quick Check:

   Loop purpose = repeat code [OK]

Hint: Loops repeat code blocks to save effort [OK]

Common Mistakes:

• Confusing loops with variables
• Thinking loops create new data types
• Believing loops stop program immediately

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

easy

A. for (int i = 0; i < 5; i++) /* code */

B. for int i = 0; i < 5; i++ { /* code */ }

C. for (int i = 0; i < 5; i++) { /* code */ }

D. for (int i = 0; i < 5; i++) [] { /* code */ }

Solution

1. Step 1: Recall the correct for loop syntax

   The for loop syntax requires parentheses around initialization, condition, and increment, followed by a block in braces.

2. Step 2: Check each option

   for (int i = 0; i < 5; i++) { /* code */ } matches the correct syntax exactly. Others miss parentheses, braces, or use wrong symbols.

3. Final Answer:

   for (int i = 0; i < 5; i++) { /* code */ } -> Option C

4. Quick Check:

   Correct for loop syntax = for (int i = 0; i < 5; i++) { /* code */ } [OK]

Hint: For loops need parentheses and braces [OK]

Common Mistakes:

• Omitting parentheses around conditions
• Missing braces for loop body
• Using wrong symbols like [] instead of {}

3. What will be the output of the following code?

int count = 0;
for (int i = 1; i <= 3; i++) {
  count += i;
}
std::cout << count;

medium

A. Error

B. 6

C. 0

D. 3

Solution

1. Step 1: Trace the loop iterations

   The loop runs with i = 1, 2, 3. Each time, count adds i: 0+1=1, 1+2=3, 3+3=6.

2. Step 2: Determine final count value

   After the loop, count is 6, which is printed.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Sum 1+2+3 = 6 [OK]

Hint: Add loop variable each iteration to sum quickly [OK]

Common Mistakes:

• Confusing loop end condition
• Forgetting to add inside loop
• Assuming count resets inside loop

4. Identify the error in this loop code:

int i = 0;
while (i < 3) {
  std::cout << i << " ";
}

medium

A. Variable i should be declared inside the loop

B. Incorrect while loop syntax

C. Missing semicolon after std::cout

D. Missing increment of i inside the loop

Solution

1. Step 1: Analyze the while loop behavior

   The loop condition is i < 3, but i never changes inside the loop, causing an infinite loop.

2. Step 2: Identify the missing increment

   To progress, i must increase inside the loop, e.g., i++.

3. Final Answer:

   Missing increment of i inside the loop -> Option D

4. Quick Check:

   Loop needs variable update to avoid infinite loop [OK]

Hint: Always update loop variable inside while loops [OK]

Common Mistakes:

• Forgetting to increment loop variable
• Thinking syntax error causes infinite loop
• Declaring variable inside loop unnecessarily

5. Consider this code snippet:

int sum = 0;
for (int i = 1; i <= 5; i++) {
  if (i % 2 == 0) continue;
  sum += i;
}
std::cout << sum;

What is the output and why?

hard

A. 9, because only odd numbers 1, 3, 5 are added

B. 15, because all numbers 1 to 5 are added

C. 10, because even numbers are added

D. 0, because continue skips all additions

Solution

1. Step 1: Understand the loop and condition

   The loop runs i from 1 to 5. If i is even, continue skips adding it to sum.

2. Step 2: Calculate sum of odd numbers

   Odd numbers are 1, 3, 5. Their sum is 1+3+5 = 9.

3. Final Answer:

   9, because only odd numbers 1, 3, 5 are added -> Option A

4. Quick Check:

   Sum odd 1+3+5 = 9 [OK]

Hint: Continue skips even numbers, sum only odds [OK]

Common Mistakes:

• Adding even numbers by mistake
• Ignoring continue statement effect
• Summing all numbers instead of filtered ones