Time Complexity

When writing algorithms it is important to understand the time efficiency of your code — how much time does it take to run your code? Using Big-O notation, comparisons can be made to determine the efficiency of different approaches to a problem by expressing how quickly the runtime grows relative to the input.

Let’s take a look at a couple examples to familiarize ourselves with Big-O notation.

var arr = [1,2,3];
for (var i = 0; i < arr.length; i++) {
console.log(arr[i);
}
// The loop will be run a total of 3 times

Here we have a for loop that iterates through an array and logs each element in the console. Since the number of iterations depends on the input (in this case, number of elements in the array), the runtime grows “on the order of the size of the input,” or in linear time (O(n)).

var arr = [1,2,3];
for (var i = 0; i < arr.length; i++) {
for (var j = 0; i < arr.length; i++) {
console.log(i + j);
}
}
// For each outer loop run, the inner loop will run 3 times.
// Total of 9 loops run

Now we are handling a nested for loop within a for loop. Since both our inner function and outer function run n times, the overall function runs in quadratic time (O(n2)).