What is Runtime Complexity?

The first time I was asked question, it was in a mock technical interview. Up until that point, I was feeling very confident in what I had done. When the interviewer asked me “What is the runtime complexity of the function you just wrote?” my response was something along the lines of “Uhhhhhhhhh”.

It was a concept that I had never heard before, so naturally, I did some research and was then so surprised at how I had never heard of runtime complexity before. This concept is so important for new and experienced Software Engineers to be familiar. The goal of this post is to introduce you to runtime complexity, and give you the tools to identify the runtime complexity of different functions.

Runtime complexity is used to describe the performance of an algorithm. It answers the question:

How much more processing time/power is required to run your algorithm if we increase the number of inputs?

Understanding this is a big deal. It’s all about efficiency and making sure your algorithms are running as fast as they can. Now in the grand scheme of things algorithms don’t take that long to run. Inefficient ones would only take like a second or two. But put that in context of a massive software company with a huge database and a near infinite number of data points that an algorithm might have to go over. Looking at it from that point of view and slow algorithms start to become a nightmare. This is why runtime complexity is important and if you’re going into an interview, it’s something you should know.

Let’s look at some examples by starting with a function that will take in a string of characters and then reverse it:

function reverse(str) {
 let reversed = ''
 for (let character of str) {
  reversed = character + reversed
 }
 return reversed
}

There are many different ways to accomplish the above task. This is one of them.

You can see in the function that the loop goes over each character in the string just one time. Therefore, it would be fair to say that as the characters of the string increase, we would need to do one additional step of work. We would refer to that as a linear runtime because there is a 1:1 relationship between the number of inputs into our algorithm, and how long it takes to process it.

Let’s take a look at an algorithm I used in a previous post, that takes in an integer and then squares it:

function square(n) {
 let result = 0
 for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
   result +=1
   }
  }
 return result
}

This is not the most efficient way to do this

Because of the nested loops, one inside another, with the variable result increasing by one each time both loops run, this greatly increases the amount of steps that happen when the function gets called. If we had an input of 2, 4 steps need to be done. If we had an input of 3, 9 steps would need to be done. An input of 4 would require 16 steps of work. This runtime can be referred to as N² or quadratic runtime.

Already you can probably guess that having to choose between linear and quadratic runtime is pretty easy when trying to find the most efficient runtime. But there are other runtimes for algorithms and we’re going to take a look at determining runtimes.

Here are some notes on different runtimes that you may encounter. There are other runtimes that exist, but in general, many of the different interview questions you might get asked will fit into one of these runtimes. Some notes on how these runtimes work:

Constant Time: No matter how many elements we are working with, the algorithm will always take the same amount of time to run.

Logarithmic Time: You have logarithmic runtime if doubling the number doesn’t double the amount of work. Searching operations usually have logarithmic time.

Linear Time: We used an example of this above, the time it takes to run the algorithm as a 1:1 relationship as the number of inputs increases. Anytime you iterate through a collection of data once, you have linear runtime.

Quasilinear Time: You have this if doubling the number of elements you are iterating over doesn’t double the amount of work. Any sorting operation usually has quasilinear time.

Quadratic Time: If every element in a collection has to be compared to every other element.

Exponential Time: If you add a single element, the processing time doubles.

In an interview setting, Exponential time is not good. If your solution runs on exponential time, that is a very big bad deal.

In looking at the image above, you can see that the different time complexities have some notation as another way to describe them. This is knows as Big O Notation, and it’s another way to referencing runtime complexity.

Being able to identify runtime or Big O is very important in an interview setting.

This comes from Stephen Grider, he does great stuff!

Runtime complexity and Big O are important to know for both new and experienced developers. It’s all about efficiency and making sure the algorithms perform as fast as they can. Knowing this for an interview setting shows that you understand the greater picture of writing algorithms and it’s something that you can expected to be asked. With a little bit of practice examples it’s pretty easy to recognize.