Home/

...

/

Example 2: Time Complexity of an Algorithm With Nested Loops

Example 2: Time Complexity of an Algorithm With Nested Loops

This example is about computing the time complexity of an algorithm that involves nested for-loops.

In the previous lesson, you learned how to calculate the time complexity of an algorithm that involves a loop. Now, you will extend the same idea to analyzing an algorithm with nested for-loops.

Nested for loop

Consider the following Rust program:

Press + to interact
Rust 1.40.0
fn main(){
    let n = 5; 
    let m = 7; 
    let mut sum = 0; 
    for i in 0..n {
        for j in 0..m {
            sum += 1; 
        }
    }
    println!("{}",sum);
    return;
}

A simple piece of code prints the number of times the increment statement runs throughout the program. Compute its time complexity.

Time complexity

Take the training wheels off, and jump straight to line 5. As seen from the previous lesson, line 5 accounts for nn operations.

Move to line 6. Since this line is nested inside the for loop on line 6, it is repeated nn times. For a single iteration of the outer for loop, how many primitive operations does this line incur? You should be able to generalize from the last lesson that the answer is mm. That means that the total number of primitive operations on line 6 are n(m)n ( m ).

How about line 7? Each time it is executed, it involves reading a variable’s value, adding two numbers, and assigning it to a variable. That’s three primitive operations. Since this line is nested inside the two loops, it is ...

Access this course and 1400+ top-rated courses and projects.