Example: Measuring Time Complexity of For Loop
In this lesson, we are going to learn how to compute the running time complexity of an algorithm that involves loops.
We'll cover the following...
Lets now calculate the running time complexity of a more complex program. We will split the code into individual operations and then compute how many times each is executed.
Simple For Loop of Size n #
Here is an example of a simple loop of size n:
Press + to interact
n = 10 # just as an example, n can be anythingsum = 0for var in range(n):sum += 1print(sum)
| Operation | Number of executions |
|---|---|
n = 10 |
1 |
sum = 0 |
1 |
range(n) |
|
var=0 |
1 |
var=1 |
1 |
var=2 |
1 |
| … |