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