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

Solution: Nested Loop With Multiplication (Advanced)

Explore how to evaluate the time complexity of nested loops where the inner loop doubles each iteration. Learn to derive the total complexity as O(n log n) through detailed breakdowns of loop behaviors and logarithmic calculations.

We'll cover the following...

Solution #

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

Solution Breakdown

The outer loop is O(n)O(n) as it iterates n times. The inner while loop iterates i times, which is always less than n and the inner loop counter variable is doubled each time. Therefore we can say that it is O(log2(n))O(log_2(n)). Thus, the total time complexity of the program given above becomes:

O(nlog2(n))O(nlog_2(n))

Here’s another way to arrive at the same result. Let’s look at the inner loop once again.

The inner loop depends upon j which is less than i and is multiplied by 2 in each iteration. This means that the complexity of the inner loop is O(log2(i))O(log_2(\text{i})). But, the value of i at each iteration, of the outer loop, is different. The total complexity of the inner loop in terms of n can be calculated as such:

n×log2(i)⇒∑i=1nlog2(i)n \times log_2(i) \Rightarrow\sum_{i=1}^{n} log_2 (i)

⇒log2(1)+ ...