Loop initialization, condition, update in Java - Time & Space Complexity

Time Complexity: Loop initialization, condition, update

O(n)

Understanding Time Complexity

We want to understand how the time a loop takes changes as we change its size.

How do the parts of a loop affect how long it runs?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (int i = 0; i < n; i++) {
    System.out.println(i);
}
    

This loop prints numbers from 0 up to n-1, running once for each number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop runs the print statement.
• How many times: Exactly n times, once for each number from 0 to n-1.

How Execution Grows With Input

As n grows, the number of times the loop runs grows the same way.

Input Size (n)	Approx. Operations
10	10 print operations
100	100 print operations
1000	1000 print operations

Pattern observation: The work grows directly with n; double n means double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows in a straight line with the size of n.

Common Mistake

[X] Wrong: "The loop runs faster because the update step is simple."

[OK] Correct: The update step is very fast, but the loop still runs n times, so the total time depends on how many times it repeats, not just the update.

Interview Connect

Understanding how loops grow with input size helps you explain your code clearly and shows you know how to think about efficiency.

Self-Check

"What if we changed the loop to count down from n to 0? How would the time complexity change?"

Practice

1. Which part of a for loop in Java sets the starting value of the loop variable?

easy

A. Initialization

B. Condition

C. Update

D. Body

Solution

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

   A for loop has three parts: initialization, condition, and update.

2. Step 2: Identify the starting value part

   The initialization part sets the starting value of the loop variable before the loop runs.

3. Final Answer:

   Initialization -> Option A

4. Quick Check:

   Starting value = Initialization [OK]

Hint: Initialization always sets the loop's start value [OK]

Common Mistakes:

• Confusing condition with initialization
• Thinking update sets the start value
• Mixing loop body with initialization

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

easy

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

B. for(int i = 0; i <= 4; i++) {}

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

D. for(int i = 0; i != 5; i--) {}

Solution

1. Step 1: Check initialization and condition

   for(int i = 0; i <= 4; i++) {} starts at 0 and runs while i is less than or equal to 4, which covers 0 to 4.

2. Step 2: Check update direction

   for(int i = 0; i <= 4; i++) {} increments i by 1 each time, moving forward correctly.

3. Final Answer:

   for(int i = 0; i <= 4; i++) {} -> Option B

4. Quick Check:

   0 to 4 inclusive = for(int i = 0; i <= 4; i++) {} [OK]

Hint: Use i <= max to include last number [OK]

Common Mistakes:

• Using i < 4 excludes 4
• Starting at 1 misses 0
• Decrementing i causes infinite loop

3. What is the output of this Java code?

for(int i = 1; i < 5; i += 2) {
    System.out.print(i + " ");
}

medium

A. 1 2 3 4

B. 1 3 5

C. 2 4

D. 1 3

Solution

1. Step 1: Trace loop values

   i starts at 1, prints 1, then i increases by 2 to 3, prints 3, then i increases by 2 to 5.

2. Step 2: Check loop condition

   Loop runs while i < 5. When i is 5, condition fails, so loop stops.

3. Final Answer:

   1 3 -> Option D

4. Quick Check:

   Prints 1 and 3 only [OK]

Hint: Add update to i and check condition carefully [OK]

Common Mistakes:

• Assuming loop runs when i equals 5
• Forgetting i increments by 2
• Printing values after loop ends

4. Identify the error in this Java loop:

for(int i = 0; i > 5; i++) {
    System.out.println(i);
}

medium

A. Condition causes loop to never run

B. Update should decrement i

C. Initialization is incorrect

D. Missing loop body braces

Solution

1. Step 1: Analyze the loop condition

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

2. Step 2: Understand loop execution

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

3. Final Answer:

   Condition causes loop to never run -> Option A

4. Quick Check:

   False condition stops loop immediately [OK]

Hint: Check if condition is true at start to run loop [OK]

Common Mistakes:

• Thinking loop runs at least once
• Confusing > with < in condition
• Assuming update fixes condition

5. You want to print all even numbers from 2 to 20 using a for loop in Java. Which loop correctly does this?

hard

A. for(int i = 2; i < 20; i++) { if(i % 2 == 0) System.out.print(i + " "); }

B. for(int i = 1; i < 20; i++) { if(i % 2 == 0) System.out.print(i + " "); }

C. for(int i = 2; i <= 20; i += 2) { System.out.print(i + " "); }

D. for(int i = 0; i <= 20; i += 2) { System.out.print(i + " "); }

Solution

1. Step 1: Check initialization and update for even numbers

   for(int i = 2; i <= 20; i += 2) { System.out.print(i + " "); } starts at 2 and increments by 2, printing even numbers directly up to 20.

2. Step 2: Verify condition includes 20

   Condition i <= 20 ensures 20 is included in output.

3. Final Answer:

   for(int i = 2; i <= 20; i += 2) { System.out.print(i + " "); } -> Option C

4. Quick Check:

   Start at 2, step 2, up to 20 [OK]

Hint: Start at first even, add 2 each time [OK]

Common Mistakes:

• Starting at 0 prints unwanted 0
• Using < 20 excludes 20
• Forgetting to increment by 2