Search⌘ K
Home
Courses
Data Structures for Coding Interviews in Python

Example: Measuring Time Complexity of a Nested For Loop

Explore how to determine the time complexity of nested for loops by analyzing each operation's execution count. Understand the combined effect of inner and outer loops to calculate the total time complexity accurately.

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.

Python 3.5
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
...