Data Structures for Coding Interviews in JavaScript/

...

/

Solution: Big (O) of Nested Loop With Addition

Solution: Big (O) of Nested Loop With Addition

This review provides a detailed analysis of the time complexity of the Nested Loop with Addition problem!

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
...