Runtime Complexity Analysis with JavaScript

There are always multiple ways to solve an algorithmic problem. However, what if we’re trying to decide which of our solutions is the best? Now, we don’t mean best in terms of how easy it might be to write the code. No, we mean best as in how efficient the code performs. How might we decide which solution is the most efficient?

Enter runtime complexity, a way to concretely determine which of our solutions is indeed better.

What is Runtime Complexity?

Runtime complexity is a term that is used to describe the performance of an algorithm.

During an interview, it is likely that you will be asked what the runtime complexity of an algorithm is. If you’ve never heard of this term before, you would probably be quite confused by the question. However, it is essential to know this topic well. Not only so you can pass interviews, either, but so that you may write more efficient code throughout your career. Luckily, runtime complexity isn’t as complicated as it may appear.

The math looks scary, but it’s not more complicated than some of the code you might have already written. To ease some of your fears of mathematics for the sake of this article, take a look the tweet below.

Some of you reading this may have just had a revelation – maybe mathematics isn’t so bad afterall!

We posted this on our Facebook page, and people couldn’t believe it. Those scary symbols are really just for loops? Yes, indeed they are. What a relief, right?!

Now that that’s out of the way, what exactly is runtime complexity?

Runtime complexity is a term that is used to describe the performance of an algorithm. We can use runtime complexity to compare different solutions to an algorithmic problem, and decide which of these solutions would be the most efficient under different circumstances (e.g. how much more time is required to run your algorithm if we doubled the input?).

Let’s look at an example from one of our previous articles.

// Iterative solution
function reverse(str) {
  let reversed = "";

  for (let character of str) {
    reversed = character + reversed;
  }

  return reversed;
}
console.log(reverse("apple"));
// Output: 'elppa'

If we look at the input of the reverse() function, we see we have a string, 'apple' with 5 characters. Our algorithm will reverse the string pretty quickly. However, for each additional character that gets added to the input, we would need to add an additional step through the loop. Our algorithms runtime would be O(N) (pronounced Big O of N, or O of N) or linear runtime – the runtime increases as the input gets larger.

There are many more runtimes other than O(N). Some of the most common being O(log N), O(N^2), and O(2^n).

• O(1) always completes in same amount of time, regardless of the input size.
• O(log N) takes a fixed additional amount of time each time the input size doubles.
• O(N) takes twice as long to finish if the input size doubles.
• O(N^2) takes four times as long if the input size doubles.
• O(2^N) increases exponentially as the input size increases.

Graphs of functions commonly used in the analysis of algorithms. Source: Wikipedia.

Determining Complexity

Below, we’ll explore some algorithms and examine what their runtimes are. We’ve already gone over an O(N) (linear) algorithm above, so we’ll jump right into a few of the others.

Quadratic Runtime

Let’s explore another algorithm from a previous article, steps.js.

function steps(num) {
  for (let row = 0; row < num; row++) {
    let stair = "";

    for (let column = 0; column < num; column++) {
      if (column <= row) {
        stair += "#";
      } else {
        stair += " ";
      }
    }
    console.log(stair);
  }
}
steps(4);

Each additional increment of the steps algorithm above requires N^2 more things to do. Thus, our runtime is O(N^2), or quadratic runtime. The algorithm will need to perform significantly more work as our input gets larger, making our algorithm rather inefficient for large quantities of data. However, it may not be so bad if our data set is small, and we know it will remain small.

Constant Runtime

Take a look at the code below, and count the number of steps that is required to run the algorithm.

function timesTwo(num) {
  return num * 2;
}
console.log(timesTwo(5)); // 10
console.log(timesTwo(1000)); // 2000

Did you count the number of steps the code above has to perform? Indeed, it’s quite simple – the code needs only to perform one operation: multiply the input by 2. Thus, we have one step. Regardless of the input, the complexity will remain the same. Therefore, we have an O(1) runtime, also called constant runtime.

Logarithmic Runtime

Let’s take a look at another common runtime, O(log N), or logarithmic runtime. In order to understand this runtime, we must return to mathematics. Don’t be alarmed – just like the scary math symbols above, logarithms are rather quite simple.

Logarithm: a quantity representing the power to which a fixed number (the base) must be raised to produce a given number.

Let’s explore an example.

$$\log_{2}(16)=x$$

The 2 is called the base of the logarithm. We need to find what power to raise the base by to get 16. $$2^x = 16$$ x in this case is going to be 4, as 2 * 2 * 2 * 2 = 16. See, these logarithms aren’t so scary after all.

Now that we got that out of the way, let’s explore an algorithm with O(log N) runtime.

function time(arr) {
  let loopCount = 0;
  for (let i = 1; i < arr.length; i *= 2) {
    loopCount++;
  }
  return loopCount;
}

The for-loop multiplies the current value of i by 2, so i goes from 1 => 2 => 4 => 8 => 16 => 32. Thus it doubles with each loop iteration. Each time the length of the arrays input is doubled, the number of steps increases by 1 each time.

The number of operations doesn’t increase a whole lot as the size of the input grows. If you look at the graph above, you’ll see that logarithmic time complexity is quite good, outperforming linear runtime, but not quite as fast as constant runtime.

More on Runtime Complexity

This article explored some fundamental concepts of runtime complexity analysis with JavaScript. After reading this article, you should be able to determine some of the runtimes of algorithms, as well as determine whether or not your own algorithms are efficient.

This article is meant to serve as a short introduction, and not meant to be a complete resource to the subject, as it is quite massive. There are many more resources available both online and in books – we’ll list some of them down below.

Recommended Resources

A Programmer’s Guide to Computer Science: A virtual degree for the self-taught developer

This book offers a pretty good introduction to various computer science topics, including runtime analysis – a must-read for self-taught developers, but also a good reference book in general. We interviewed William Springer, the author of this book. You can read it here.

Cracking the Coding Interview

Cracking the Coding Interview has an extensive chapter related to runtime analysis, but also explores many more algorithms and dissects their runtimes. If you want to become extremely knowledgable in the subject, this book is a must-have. We wrote an in-depth review here.

More on Logarithms

This article is provided by Khan Academy and explores logarithms more in depth.

Analysis of Algorithms - Video Lectures

15+ hours of video instruction. These video lectures cover the essential information that every serious programmer needs to know about analyzing algorithms

Full Disclosure: this post contains affiliate links. However, we only recommend books or products (courses) that we have personally read or used. We may receive a (very) small commission if you purchase any of the books or courses from this list (at no additional cost to you).