Data Structures for Coding Interviews in JavaScript/

...

/

Example: Measuring Time Complexity of a Single Loop Algorithm

Example: Measuring Time Complexity of a Single Loop Algorithm

In this lesson, we are going to learn how to compute the time complexity of an algorithm that involves a for loop.

We'll cover the following...

A For Loop With n Iterations

Now, let’s consider what happens when a loop is involved. Consider the following javascript program:

Press + to interact
// just as an example, n can be anything
var n = 10 
var sum = 0
// for loop
for(var i=0;i<n;i++)
  sum+=2
console.log(sum)

Let’s count the number of primitive operations in the above program. We skip the non-executable lines and come to lines 2 and 3 where variable initializations are taking place, which account for one primitive operation, each.

Line 6 is a loop statement. To count the number of primitive operations on that line, we must dissect it into its constituents: the initialization, the increment, and the test. The initialization occurs only once and is counted as one primitive operation. The increment (i++i++) operation must read the current value of variable ii, add 11 to it and store the result back in variable ii. That’s three primitive operations. The test operation (i<ni < n ...