Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Example: Measuring Time Complexity—Nested Loop

Explore how to analyze the time complexity of nested loops by breaking down code execution step-by-step. Understand how to apply asymptotic analysis and Big O notation to assess algorithm efficiency in C#.

We'll cover the following...

A nested loop

We will extend the previous example and make it a little harder by adding a “nested loop” in the ...

C# 9.0
int n = 5; // 'n' can be anything
int sum = 0;
        
for (int i = 0; i < n; i++)
{
    for (int j = 0; j < n; j++)
    {
        sum += 1;
    }
}
System.Console.WriteLine(sum);

Running time complexity

We will first break this program into individual operations like this:

Statement

Number of Executions

n = 5

11

sum = 0

11

for (int i = 0; i < n; i++) line 4

11

i = 0

11

i = 1

11

i = 2

11

...

i = n

11

for (int j = 0; j < n; j++) line 6

n×1n \times 1

j = 0

1×n1\times n

j = 1

1×n1\times n

j = 2

1×n1\times n

...

j = n

1×n1\times n

sum+=1

(3n)×n(3n) \times n

System.Console.WriteLine(sum)

11

Total

5n2+2n+35n^2 + 2n + 3

We’re multiplying ...