Data Structures for Coding Interviews in Python/

...

/

Example: Measuring Time Complexity of a Nested For Loop

Example: Measuring Time Complexity of a Nested For Loop

Compute time complexity of a given algorithm with nested loops.

We'll cover the following...

A Nested Loop

Now 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
n = 5  # n can be anything
sum = 0
for i in range(n):
    for j in range(n):
        sum += 1
print(sum)

Time Complexity

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

Statement Number of Executions
n = 5 1
sum = 0 1
range(n) line 3 11
i = 0 1
i = 1 1
i = 2 1
…
i = n - 1 1
range(n) line 4 n×1n \times 1
j = 0 1×n1\times n
j = 1 1×n1\times n
j = 2 1×n1\times n
...