Home/

...

/

Solution Review: Nested Loop with Multiplication (Advanced)

Solution Review: Nested Loop with Multiplication (Advanced)

This review provides a detailed analysis of how to solve the "Nested Loop with Multiplication" challenge

Solution #

Press + to interact
Rust 1.57.0
fn main(){
    let n = 10; 
    let mut sum = 0; 
    let _pie = 3.14; 
    for i in 0..n{ // O(n)
        let mut j = 1; // O(n)
        while j < i { // O(log(n!))
            sum += 1; // O(log(n!))
            j *= 2; // O(log(n!))
        }
    }
    println!("{}",sum);
}

In the main function, the outer loop is O(n)O(n) as it iterates n times. The inner while loop iterates i times, which is always less than n and the inner loop counter variable is doubled each time. Therefore, you can say that it is O(log2(n))O(log_2(n)). The total time complexity of the program given above becomes:

O(nlog2(n))O(nlog_2(n))

Here’s another way to arrive at the same result. Let’s look at the inner loop once again.

The inner loop depends upon j, which is less than i, and is multiplied by 2 in each iteration. This means that the complexity of the inner loop is O(log2(i))O(log_2(\text{i})). But the value of i at each iteration of the outer loop is different. The total complexity of the inner loop in terms of n can be calculated as such:

n×log2(i)⇒∑i=1nlog2(i)n \times log_2(i) \Rightarrow\sum_{i=1}^{n} log_2 (i) ...

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