Solution Review: Nested Loop with Multiplication (Basic)

Solution #

The code for this challenge is reproduced below:

Press + to interact

Rust 1.57.0

fn main(){
    let n = 10; 
    let mut sum = 0; 
    let mut counter = 1; 
    let pie = 3.14; 
    while counter < n { // O(log(n))
        println!("{}", pie);  // O(log(n))
        for _j in (1..n).step_by(2){  // O(log(n))*O(n)
            sum += 1; // O(log(n))*O(n)
        }
        counter *= 3; // O(log(n))
    }
    println!("{}", sum);
}

Time complexity

Here’s a table that lists the running time line-by-line.

Statement	Number of Executions
`let n = 10;`	1
`let mut sum = 0;`	1
`let mut counter = 1;`	1
`let pie = 3.14;`	1
`while counter < n`	$log_3(n)$
`println!("{}",pie);`	$log_3(n)$
`let mut j=1;`	$log_3(n)$
`for _j in (1..n).step_by(2);`	$log_3(n) *\frac{n}{2}$
`sum+=1;`

...

Introduction to Complexity Measures

Rust Pointers

Introduction to Arrays

Introduction to Linked Lists

Introduction to Stack/Queues

Introduction to Graphs

Introduction to Trees

Trie

Introduction to Heap

Introduction to Hashing

Summary of Data Structures

Solution Review: Nested Loop with Multiplication (Basic)

Solution #

Time complexity