Loop execution flow - Time & Space Complexity

Time Complexity: Loop execution flow

O(n)

Understanding Time Complexity

Loops are a basic way to repeat actions in code. Understanding how many times a loop runs helps us see how long a program might take.

We want to know how the work grows as the loop runs more times.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (int i = 0; i < n; i++) {
    printf("%d\n", i);
}
    

This code prints numbers from 0 up to n-1, repeating the print action n times.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The print statement inside the loop.
• How many times: Exactly n times, once for each loop cycle.

How Execution Grows With Input

As n gets bigger, the number of print actions grows the same way.

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

Pattern observation: The work grows directly with n, so doubling n doubles 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 as n gets bigger because computers are fast."

[OK] Correct: Even though computers are fast, the loop still does more work when n is bigger, so it takes more time overall.

Interview Connect

Knowing how loops affect time helps you explain your code clearly and shows you understand how programs grow with input size.

Self-Check

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

Practice

1. Which loop in C always executes its body at least once, regardless of the condition?

easy

A. do-while loop

B. for loop

C. while loop

D. if statement

Solution

1. Step 1: Understand loop types

   The do-while loop checks its condition after running the loop body once.

2. Step 2: Compare with other loops

   The for and while loops check the condition before running the body, so they may not run at all.

3. Final Answer:

   do-while loop -> Option A

4. Quick Check:

   do-while runs body once before condition check [OK]

Hint: do-while runs body first, then checks condition [OK]

Common Mistakes:

• Thinking for or while loops always run once
• Confusing if statement with loops
• Assuming do-while checks condition first

2. Which of the following is the correct syntax for a for loop in C that counts from 0 to 4?

easy

A. for (i < 5; i = 0; i++) {}

B. for i = 0 to 4 {}

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

D. for (int i = 0; i <= 5; i++) {}

Solution

1. Step 1: Check for loop syntax

   The correct syntax is for (initialization; condition; increment). for (int i = 0; i < 5; i++) {} matches this.

2. Step 2: Validate loop range

   for (int i = 0; i < 5; i++) {} counts i from 0 up to but not including 5, so 0 to 4.

3. Final Answer:

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

4. Quick Check:

   Standard for loop syntax with i from 0 to 4 [OK]

Hint: for loops use (init; condition; increment) syntax [OK]

Common Mistakes:

• Using 'for i = 0 to 4' which is not C syntax
• Swapping condition and initialization
• Using <= 5 to count 0 to 4 (includes 5)

3. What is the output of this C code?

int i = 0;
while (i < 3) {
    printf("%d ", i);
    i++;
}

medium

A. 0 1 2

B. 1 2 3

C. 0 1 2 3

D. 3 2 1 0

Solution

1. Step 1: Analyze loop condition and variable

   Variable i starts at 0 and increments by 1 each loop while i < 3.

2. Step 2: Trace output values

   Loop runs for i = 0, 1, 2 printing each value followed by a space.

3. Final Answer:

   0 1 2 -> Option A

4. Quick Check:

   while loop prints 0,1,2 then stops [OK]

Hint: Check loop condition carefully to count printed values [OK]

Common Mistakes:

• Including 3 in output by mistake
• Starting count from 1 instead of 0
• Printing after increment instead of before

4. Identify the error in this loop code:

int i = 0;
while (i < 5) {
    printf("%d ", i);
}

medium

A. Incorrect printf format specifier

B. Missing increment of i inside the loop

C. Condition should be i <= 5

D. Variable i should be declared inside the loop

Solution

1. Step 1: Check loop body for changes to i

   The variable i is never incremented inside the loop, so i stays 0 forever.

2. Step 2: Understand loop consequence

   Without increment, the condition i < 5 is always true, causing an infinite loop.

3. Final Answer:

   Missing increment of i inside the loop -> Option B

4. Quick Check:

   Infinite loop due to no i++ [OK]

Hint: Always update loop variable to avoid infinite loops [OK]

Common Mistakes:

• Thinking condition is wrong instead of missing increment
• Assuming printf format is incorrect
• Declaring i inside loop is optional, not error

5. Consider this nested loop:

for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= i; j++) {
        printf("%d", j);
    }
    printf("\n");
}

What is the output?

hard

A. 1
22
333

B. 1
2
3

C. 123
123
123

D. 1
12
123

Solution

1. Step 1: Understand outer loop iterations

   The outer loop runs i from 1 to 3, inclusive, so 3 times.

2. Step 2: Trace inner loop for each i

   For each i, inner loop runs j from 1 to i, printing j values without spaces.

3. Step 3: Combine outputs

   Lines printed are:
   i=1: "1"
   i=2: "12"
   i=3: "123"
   Each followed by newline.

4. Final Answer:

   1 12 123 -> Option D

5. Quick Check:

   Nested loops print increasing sequences per line [OK]

Hint: Inner loop runs up to outer loop counter each time [OK]

Common Mistakes:

• Confusing inner loop range with outer loop
• Printing j values incorrectly
• Missing newline after each inner loop