Solution Review: Nested Loop with Multiplication (Intermediate)

Solution #

Press + to interact

Rust 1.57.0

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

The outer loop index i goes: $1,3,6,9,\cdots,n$ . That means that the outer loop has $\frac{n}{3}$ iterations.
The inner loop index j goes: $1,3,9,27,\cdots,n$ . That means that an inner loop has $log_3(n)$ iterations. ...

Statement	Number of Executions
`let n = 10;`	1
`let mut sum = 0;`	1
`let j = 1;`	1
`let pie = 3.14;`	1
`for _i in (1..n).step_by(3)`	$\frac{n}{3}$
`println!("{}",pie);`	$\frac{n}{3}$

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 (Intermediate)

Solution #