What Is the Runtime Complexity or Big ‘O’ Notation?

You probably heard a lot about runtime complexity and how this can help you to build better code and solution, but what is the run time complexity???

You probably experience in your coding journey moments where you had to implement a function to solve a problem in your project, or maybe you solved some challenges using a solution and later seeing a hundred of different solutions. So what is the difference between the solutions and how can you measure which one is best then another? .This is where runtime complexity comes in play.

Runtime complexity is way to describes the performance of an algorithm, or how much more processing power/time is required to run the algorithm, and what happens if we double the input?. Runtime complexity compares different solutions to a given problem or different algorithms.

This is one of the most common and often asked questions, and you should be able to identify the run time complexity of the solutions you implemented and how can you improve where is possible.

Linear runtime O(n)

Let see a simple example of finding the right dog for you.

To solve this challenge, we are iterating into each dog one time, and this means that for each dog added to our array, the filter method has to do some additional work. So 1 dog = 1 extra step.

We can say that it is a solution that has a complexity of “N” or “linear” runtime.

Quadratic runtime o(n²)

Let’s see another challenge the steps algorithm, that you can find here,

In this challenge we have and N input, and based on this input, we have 2 nested loops. This means that for each “N” input we have to do some additional work, but this time we have two for loop has to iterate through our input. But how much work we have to do this time?.

In this example, our solution for an input N= 2 has to do 4 things and for the input of N =3 the work increased from 4 to 9, and if insert an input N =4, the steps to do increased to 16.

In this solution, every time we increase the input by one, we have to do a significant amount of additional steps and is clear that is not a 1 to 1 relation between the input and the algorithm. We can say that the amount of work had to do N squared O(n²) = (2², 3², 4²) or quadratic runtime.

Other types of common run time

So far, we saw and discuss many different types of time complexity, but another way to referencing this topic is the Big ‘O’ Notation. It’s really common to hear both terms, and you need to know that are bot refereeing to the time complexity or the efficiency of your algorithm, Example:

Linear time = O(n)

Constatn time = O(1)

Quadratic time = O(n²)

The O, in this case, stand for Big ‘O’, because is literally a big O.

Now I want to share some tips to identify the run time complexity of an algorithm. This is not a rule that you must follow, but a simple little guide that can help or direct you in the right way.

I hope you enjoyed my little introduction to Big O notation, in case, please leave a clap and share your feedback :)