Algorithms for Coding Interviews in C#/

...

/

Example: Measuring Time Complexity—Nested Loop

Example: Measuring Time Complexity—Nested Loop

Learn to compute time complexity of a given algorithm that involves nested loops.

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 program. We will calculate its time complexity by following the same series of steps that we did in the previous example. Let’s take a look at the following example. It is a simple piece of code that prints the number of times the increment statement runs throughout the program. Let’s compute its time complexity.

Press + to interact
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 ...