Nested loop execution in C Sharp (C#) - Time & Space Complexity

Time Complexity: Nested loop execution

O(n²)

Understanding Time Complexity

When we have loops inside loops, the time it takes to run the code can grow quickly.

We want to understand how much longer the program runs as the input size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        Console.WriteLine(i * j);
    }
}
    

This code prints the product of i and j for every pair of numbers from 0 to n-1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner loop's print statement runs repeatedly.
• How many times: The inner loop runs n times for each of the n iterations of the outer loop, so total n x n times.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	100
100	10,000
1000	1,000,000

Pattern observation: When n doubles, the number of operations grows by about four times because the loops multiply.

Final Time Complexity

Time Complexity: O(n²)

This means the time to run the code grows roughly with the square of the input size.

Common Mistake

[X] Wrong: "The inner loop only adds a small extra time, so the total time is just O(n)."

[OK] Correct: Because the inner loop runs completely for each outer loop step, the total work multiplies, not adds.

Interview Connect

Understanding nested loops helps you explain how your code scales and shows you can spot costly operations.

Self-Check

"What if the inner loop ran only up to a fixed number instead of n? How would the time complexity change?"

Practice

1. What happens when you use a nested loop in C#?

easy

A. Both loops run at the same time independently.

B. The outer loop runs only once and the inner loop runs multiple times.

C. The loops run only if a condition outside the loops is true.

D. The inner loop runs completely for each iteration of the outer loop.

Solution

1. Step 1: Understand nested loop structure

   In nested loops, the outer loop controls how many times the inner loop runs fully.

2. Step 2: Analyze loop execution order

   For each iteration of the outer loop, the inner loop runs from start to finish before the outer loop moves to the next iteration.

3. Final Answer:

   The inner loop runs completely for each iteration of the outer loop. -> Option D

4. Quick Check:

   Nested loops = inner loop runs fully each outer loop [OK]

Hint: Inner loop finishes all steps per outer loop step [OK]

Common Mistakes:

• Thinking both loops run simultaneously
• Assuming outer loop runs only once
• Confusing loop execution order

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

easy

A. for(int i = 0; i < 3; i++) { for(int j = 0; j < 2; j++) { Console.WriteLine(i + j); } }

B. for i in range(3) { for j in range(2) { Console.WriteLine(i + j); } }

C. for(int i = 0; i < 3; i++) for(int j = 0; j < 2; j++) Console.WriteLine(i + j); }

D. foreach(int i = 0; i < 3; i++) { foreach(int j = 0; j < 2; j++) { Console.WriteLine(i + j); } }

Solution

1. Step 1: Check C# for loop syntax

   The correct for loop uses parentheses with initialization, condition, and increment separated by semicolons.

2. Step 2: Verify nested loop braces and statements

   for(int i = 0; i < 3; i++) { for(int j = 0; j < 2; j++) { Console.WriteLine(i + j); } } correctly nests two for loops with braces and valid syntax. Other options use incorrect syntax or keywords.

3. Final Answer:

   for(int i = 0; i < 3; i++) { for(int j = 0; j < 2; j++) { Console.WriteLine(i + j); } } -> Option A

4. Quick Check:

   C# for loop syntax = for(int i = 0; i < 3; i++) { for(int j = 0; j < 2; j++) { Console.WriteLine(i + j); } } [OK]

Hint: Remember C# for loop uses semicolons inside parentheses [OK]

Common Mistakes:

• Using Python-like syntax in C#
• Missing semicolons in for loop
• Using foreach incorrectly for numeric loops

3. What is the output of this C# code?

for(int i = 1; i <= 2; i++) {
  for(int j = 1; j <= 3; j++) {
    Console.Write(i * j + " ");
  }
  Console.WriteLine();
}

medium

A. 6 12

B. 1 2 3
2 4 6

C. 1 1 1
2 2 2

D. 1 2 3 4 5 6

Solution

1. Step 1: Trace outer loop values

   Outer loop i runs from 1 to 2 (two iterations).

2. Step 2: Calculate inner loop outputs per i

   For i=1, inner loop j=1 to 3 outputs 1*1=1, 1*2=2, 1*3=3. For i=2, inner loop outputs 2*1=2, 2*2=4, 2*3=6.

3. Final Answer:

   1 2 3 2 4 6 -> Option B

4. Quick Check:

   Nested loops multiply i and j = output lines [OK]

Hint: Multiply outer and inner loop counters for output [OK]

Common Mistakes:

• Confusing loop ranges
• Printing without spaces or newlines
• Mixing up i and j in multiplication

4. Identify the error in this nested loop code:

for(int i = 0; i < 3; i++) {
  for(int j = 0; j < 2; j++)
    Console.WriteLine(i + j);
  }
}

medium

A. Extra closing brace '}' after the inner loop.

B. Missing semicolon after Console.WriteLine statement.

C. Incorrect loop condition in the outer loop.

D. Variable j is not declared.

Solution

1. Step 1: Check braces matching

   There is an extra closing brace '}' after the inner loop which causes a syntax error.

2. Step 2: Verify other syntax elements

   Console.WriteLine has correct syntax, loops have valid conditions, and variables are declared properly.

3. Final Answer:

   Extra closing brace '}' after the inner loop. -> Option A

4. Quick Check:

   Brace mismatch = syntax error [OK]

Hint: Count opening and closing braces carefully [OK]

Common Mistakes:

• Ignoring extra or missing braces
• Assuming missing semicolon error
• Confusing variable declaration errors

5. You want to print a multiplication table from 1 to 3 using nested loops in C#. Which code correctly prints the table with rows and columns aligned?

hard

A. for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { Console.Write(i*j); } Console.WriteLine(); }

B. for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { Console.WriteLine(i*j); } }

C. for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { Console.Write($"{i*j,4}"); } Console.WriteLine(); }

D. for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { Console.WriteLine($"{i}*{j}={i*j}"); } Console.WriteLine(); }

Solution

1. Step 1: Understand formatting for aligned output

   Using Console.Write with format specifier {value,4} aligns numbers in columns with 4 spaces width.

2. Step 2: Check nested loop and output structure

   for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { Console.Write($"{i*j,4}"); } Console.WriteLine(); } prints products in a grid with spaces, then moves to next line after inner loop finishes, creating a table.

3. Final Answer:

   for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { Console.Write($"{i*j,4}"); } Console.WriteLine(); } -> Option C

4. Quick Check:

   Formatted nested loops print aligned multiplication table [OK]

Hint: Use Console.Write with alignment specifier for columns [OK]

Common Mistakes:

• Using Console.WriteLine inside inner loop causing new lines
• Not formatting output for alignment
• Missing Console.WriteLine after inner loop