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

Example: Measuring Time Complexity of a Single Loop Algorithm

Explore how to measure the time complexity of a single loop algorithm by counting primitive operations in JavaScript. Understand how initialization, increment, and test operations contribute to overall running time and learn to compute the algorithm's time complexity accurately.

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:

Node.js
// 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 ...