...

/

Solution Review: Big (O) of Nested Loop with Addition

Solution Review: Big (O) of Nested Loop with Addition

This review provides a detailed analysis of the time complexity of the "Nested Loop with Addition" problem.

Solution

Press + to interact
Rust 1.40.0
fn main(){
let n = 10;
let mut sum = 0;
let pie = 3.14;
for i in (0..n).step_by(3){ // O(n/3)
println!("{}",pie); // O(n/3)
for j in (0..n).step_by(2){ // O(n/3)*O(n/2)
sum=sum+i; // O(n/3)*O(n/2)
println!("{}",sum); // O(n/3)*O(n/2)
}
}
}

See the following table for a detailed line-by-line analysis of the calculation of time complexity.

Statement
Number of Executions
let n = 10;
1
let mut sum = 0;
1
let pie = 3.14;
1
for i in (0..n).step_by(3)
n3\frac{n}{3}
println!("{}",pie);
n3\frac{n}{3}
for j in (0..n).step_by(2)
n3\frac{n}{3} * n2\frac{n}{2}
sum=sum+i;
n3\frac{n}{3}
...
Access this course and 1400+ top-rated courses and projects.