Example: Measuring Time Complexity - Nested Loop
Compute time complexity of a given algorithm with 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
n = 5 # n can be anythingsum = 0for i in range(n):for j in range(n):sum += 1print(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 |
|
i = 0 |
1 |
i = 1 |
1 |
i = 2 |
1 |
| … | |
i = n |
1 |
range(n) line 4 |
|
j = 0 |
|
j = 1 |
|
j = 2 |