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

Solution: Nested Loop With Multiplication (Intermediate)

Explore the analysis of nested loops where the outer loop increments by a fixed step and the inner loop multiplies the index. Learn how to derive the number of iterations and calculate the overall time complexity, including transforming logarithm bases to express Big O notation clearly, enhancing your understanding of algorithm efficiency.

We'll cover the following...

Solution #

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

  • The outer loop index i goes: 1,4,7,10,⋯ ,n1,4,7,10,\cdots,n. That means that the outer loop has n3\frac{n}{3} iterations

  • The inner loop index j goes: 1,3,9,27,⋯ ,n1,3,9,27,\cdots,n. That means that a complete run of the inner loop has log3(n)log_3(n) iterations. ...

Statement Number of Executions
const n = 10
1
let sum = 0
1
var j = 1
1
const pie = 3.14
1
var i=1
11
i<n
n3+1\frac{n}{3}+1
i+=3
n3\frac{n}{3}
console.log(pie)