Search⌘ K
Home
Courses
Data Structures for Coding Interviews in JavaScript

Solution: Nested Loop With Multiplication (Pro)

Explore how to analyze time complexity for nested loops involving multiplication using Big O notation. Learn to calculate the total number of executions and simplify the time complexity to O(n) by considering logarithmic inner loops and constant factors.

We'll cover the following...

Solution #

Node.js
const n = 10;
const pie = 3.14;
let sum = 0;
var j = 1;
for (var i = 0; i < n; i++) {
    console.log(pie);
    while (j < i) {
        sum += 1;
        j *= 2;
    }
}
console.log(sum)

The outer loop in the main function has n iterations as it iterates on i from 0 to n-1. If the condition j < i is true, the inner loop is entered. However, immediately, j is doubled. Note that j is not reset to 1 in the code since the j is immediately doubled, therefore inner while loop will run O(log2(n))O(log_2(n)) times for all the iterations of the outer loop.

Note: Inner while loop will run at most once for each iteration of the outer loop. ...

Statement Number of Executions
const n = 10
1
let sum = 0
1
var j = 1
1
const pie = 3.14
1
var i=0
11
i<n
n+1n+1
i++