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 every statement of the inner loop with nn because the outer loop runs it nn times

Also, note that while for executes only once, its execution cost is nn, i.e., each call to for results in n individual operations.

Time Complexity\text{Time Complexity} ...