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

Solution: Nested Loop With Multiplication (Basic)

Explore how to analyze the time complexity of nested loops involving multiplication in JavaScript. Understand step-by-step execution counts and how to derive Big O complexity using logarithmic functions for efficient algorithm design.

We'll cover the following...

Solution #

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

Time Complexity

The outer loop in this problem runs log3(n)log_3(n) times since i will first be equal to 11, then 33, then 6, then 9,⋯9,\cdots, until it is 3k3^k such that 3k<n3^k < n. In the inner loop, var j=1; runs log3(n)log_3(n) times, j<n gets executed log3(n)×(n2+1)log_3(n)\times(\frac{n}{2}+1) times and j+=2 executed log3(n)×n2log_3(n)\times\frac{n}{2} times. The sum+=1; line also runs a total of log3(n)×n2log_3(n)\times\frac{n}{2} ...