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

Solution: Big (O) of Nested Loop With Addition

Explore the process of deriving the Big O time complexity of nested loops with addition statements in JavaScript. Learn how to analyze each loop's execution count, combine them for total runtime, and simplify to the final O(n squared) complexity for better algorithm evaluation.

We'll cover the following...

Solution #

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

On line 6 in the outer loop, var i=1; runs once, i<n; gets executed n3+1\frac{n}{3}+1 times and i+=3 executed n3\frac{n}{3} times. In the inner loop, var j=1; gets executed n3\frac{n}{3} times in total. j<n; executes n3×(n2+1)\frac{n}{3} \times (\frac{n}{2} +1) times and j+=2 gets executed n3×n2\frac{n}{3} \times \frac{n}{2} times. Study the following table for a more detailed line-by-line analysis of the calculation of time complexity.

Statement
Number of Executions
const n = 10
1
var sum = 0
1
const pie = 3.14
1
var i=1
11
i<n
n3+1\frac{n
...