Summary
We are going to learn the top algorithm’s running time that every developer should be familiar. Knowing these time complexities will help you to assess if your code will scale. Also, it’s handy to compare different solutions for the same problem. You would be able to estimate which one will perform better.
In the previous post, we saw how Alan Turing save millions of lives with an optimized algorithm. In most common cases, fast algorithms can save you time, money and enabled new technology. So, It is paramount to know how to measure algorithms performance.
To recap time complexity estimates how well an algorithm performs regardless kind of machine is run on. You can obtain the time complexity by counting the number of elementary operations performed by your code. This time complexity is expressed as a function of the input size n
using BigO notation. n
indicates the size of the input while O is the growth rate function.
The BigO notation is used to classify algorithms based on their running time or space (memory used) as the input grows. The O
function is the growth rate in function of the input size n
.
Before we dive in, here is the big O cheatsheet and examples that we are going to cover on this post. Click on them to go directly to the implementation 😉
Big O Notation  Name  Example(s) 

O(1)  Constant  # Odd or Even number, # Lookup table (on average) 
O(log n)  Logarithmic  # Finding element on sorted array with binary search 
O(n)  Linear  # Find max element in unsorted array, # Duplicate elements in array with Hash Map 
O(n log n)  Linearithmic  # Sorting elements in array with merge sort 
O(n^{2})  Quadratic  # Duplicate elements in array (naïve), # Sorting array with bubble sort 
O(n^{3})  Cubic  # 3 variables equation solver 
O(2^{n})  Exponential  # Find all subsets 
O(n!)  Factorial  # Find all permutations of a given set/string 
Now, Let’s go one by one and provide code examples!
This post is part of a tutorial series:
Learning Data Structures and Algorithms (DSA) for Beginners
 Intro to Algorithm’s Time Complexity and Big O Notation
 Eight Time Complexities that Every Programmer Should Know 👈 you are here
 Analysis of Recursive Algorithms
O(1)  Constant time
O(1)
describes algorithms that have that takes the same time compute regardless of the input size.
For instance, if a function takes the same time to process 10 elements as well as 1 million items, then we say that it has a constant growth rate or O(1)
. Let’s see some examples.
Odd or Even
Find if a number is odd or even.


Advanced note: you could also replace n % 2
with the bit AND operator: n & 1
. If the first bit (LSB) is 1
then is odd otherwise is even.
It doesn’t matter if n is 10
or 10,001
, it will execute line 2 only one time.
Do not be fool by oneliners. They don’t always translate to constant times. You have to be aware of how they are implemented.
If you have a method like Array.sort()
or any other array or object methods you have to look into the implementation to determine its running time.
Primitive operations like sum, multiplication, substraction, division, modulo, bit shift, etc have a constant runtime. This can be shocking!
If you use the schoolbook long multiplication algorithm, it would take O(n^{2})
to multiply two numbers. However, most programming languages limit numbers to a max value (e.g. in JS: Number.MAX_VALUE
is 1.7976931348623157e+308
). So, you cannot operate numbers that yield a result greater than the MAX_VALUE
. So, primitive operations are bound to be completed on a fixed amount of instructions O(1)
or throw overflow errors (in JS, Infitity
keyword).
This example was easy. Let’s do another example.
Lookup table
Given a string find its word frecency data.


Again, we can be sure that even if the dictionary has 10 or 1 million words, it would still execute line 4 only one time to find the word. However, if we decided to store the dictionary as an array rather than a hash map, then it would be a different story. In the next section, we are going to explore what’s the running time to find an item in an array.
Only a hash table with a perfect hash function will have a worstcase runtime of O(1). The perfect hash function is not practical, so there will be some collitions and workarounds leads to a worstcase runtime of O(n). Still, on average the lookup time is O(1).
O(n)  Linear time
Linear running time algorithms are very common. It implies visiting every element from the input in the worstcase scenario.
Linear time complexity means that as the input grows, the algorithms take proportionally longer to complete. A function with a linear time complexity has a growth rate O(n)
. Let’s do an example:
Largest item on an unsorted array
Let’s say you want to find the maximum value from an unsorted array.


How many operations will the findMax
function do?
Well, it checks every element from n
. If the current element is bigger than max
it will do an assignment.
Notice that we added a counter so it can help us count how many times the inner block is executed.
If you get the time complexity it would be something like this:
 Line 23: 2 operations
 Line 4: a loop of size n
 Line 68: 3 operations inside the forloop.
So, this gets us 3(n) + 2
.
Applying the asymptotic analysis that we learn in the previous post, we can only leave the most significant term, thus: n
. And finally using the Big O notation we get: O(n)
.
We can verify this empiracally using our counter
. If n
has 3 elements:


or if n
has 9 elements:


Now imagine that you have an array of one million items. Do you think it will take the same time? Of course not, it will take longer proportionally to the size of the input. If we plot it n and findMax
running time we will have a graph precisely like a linear equation.
O(n^2)  Quadratic time
A function with a quadratic time complexity has a growth rate n^2. If the input is size 2, it will do roughly 4 operations. If the input is size 8, then it will take 64, and so on. Here are some code examples of quadratic algorithms
Has duplicates
You want to find duplicate words in an array. A naïve solution will be the following:


Time complexity analysis:
 Line 23: 2 operations
 Line 56: doubleloop of size n, so
n^2
.  Line 713: has ~3 operations inside the double
We get 3n^2 + 2
.
Again, using asymptotic analysis, we drop all constants and leave the most significant term: n^2
. So, in big O notation, it would be O(n^2)
.
We are using a counter variable to help us verify. The hasDupliates
function has two loops. If we have an input of 4 words, it will execute the inner block 16 times. If we have 9 will perform counter 81 times and so forth.


and with n size 9:


Let’s see another example.
Bubble sort
We want to sort the elements in an array.


Also, you might notice that for a colossal n
, the time it takes to solve the problem increases a lot. Can you spot the relationship between nested loops and the running time? When a function has a single loop, it usually translates to a running time complexity of O(n). Now, this function has 2 nested loops and quadratic running time: O(n^2).
O(n^c)  Polynomial time
Polynomial running is represented as O(n^c), when c > 1. As you already saw, two inner loops almost translate to O(n^2) since it has to go through the array twice in most cases. Are three nested loops cubic? In most cases, yes!
Usually, we want to stay away from polynomial running times (quadratic, cubic, O(n^c) …) since they take longer to compute as the input grows fast. However, they are not the worst. Let’s something that it’s even slower.
Triple nested loops
Let’s say you want to find the solutions for a multivariable equation that looks like this:
3x + 9y + 8z = 79
This naive program will give you all the solutions that satisfy the equation where x
, y
and z
< n
.


This algorithm has a cubic running time: O(n^3)
.
Note: We could do a more efficient solution but for the purpose of showing an example of a cubic runtime is good enough.
O(log n)  Logarithmic time
Logarithmic time complexities usually apply to algorithms that divide problems in half every time. For instance, let’s say that we want to look for a person in an old phone book. It has every name sorted alphabetically. There are at least two ways to do it:
Algorithm A:
 Start at the beginning of the book and go in order until you find the person you are looking for. Runtime:
O(n)
Algorithm B:
 Open the book in the middle and check the first name on it
 If the name that you are looking for is alphabetically bigger, then look to the right, otherwise look in the left half.
Binary search
Find the index of an element in a sorted array.
If we implement (Algorithm A) going through all the elements in an array, it will take a running time of O(n)
. Can we do better? Let’s try using the fact that the collection is already sorted and divide in half as we look for the element in question.


Calculating the time complexity of indexOf
is not as straightforward as the previous examples. This function is recursive.
There are several ways to analyze recursive algorithms. For simplicity, we are going to use the Master Method
.
Master Method for recursive algorithms
Finding the runtime of recursive algorithms is not as easy as counting the operations as we did in previous examples. The Master Method helps us to determine the runtime of recursive algorithms. We are going to explain the Master Method using the indexOf
function as an example.
When analyzing recursive algorithms, we care about these 3 things:
 Runtime of the work done outside the recursion (line 34):
O(1)
 How many recursive calls the problem is divided (line 11 or 14):
1
recursive call. Notice only one or the other will happen, never both.  How much
n
is reduced on each recursive call (line 10 or 13):1/2
. Every recursive call cutsn
in half.
1) The Master Method formula is the following:
T(n) = a T(n/b) + f(n)
where:
n
: size of the recursion problem. duh? :)a
: the number of subproblems. For our case, we only split the problem into another subproblem.b
: the factor by whichn
is reduced. For our case, we dividen
in half each time.f(n)
: the running time outside the recursion. E.g., O(1)
2) Once we know the values of a
, b
and f(n)
. We can determine the runtime of the recursion using this formula:
n^{logba}
This value will help us to find which mater method case we are solving.
3) Finally, we compare the recursion runtime from step 2) and the runtime f(n)
from step 1). Based on that we have the following cases:
Case 1: Most of the work in done in the recursion.
If n^{logba}
> f(n)
,
then then runtime is:
O(n^{logba})
Case 2: The runtime of the work done in the recursion and outside is the same
If n^{logba}
=== f(n)
,
then then runtime is:
O(n^{logba} log(n))
Case 3: Most of the work is done outside the recursion
If n^{logba}
< f(n)
,
then then runtime is:
O(f(n))
Now, let’s combine everything we learned here to get the running time of our binary search function indexOf
.
Master Method for Binary Search
The binary search algorithm slit n
on half until a solution is found or array is exhausted. So, using the Master Method:
T(n) = a T(n/b) + f(n)
1) Find a
, b
and f(n)
and replace it in the formula:
a
: the number of subproblems. For our example, we only split the problem into another subproblem. Soa=1
.b
: the factor by whichn
is reduced. For our case, we dividen
in half each time. Thus,b=2
.f(n)
: the running time outside the recursion:O(1)
.
Thus,
T(n) = T(n/2) + O(1)
2) Compare the runtime executed inside and outside the recursion:
 Runtime of the work done outside the recursion:
f(n)
. E.g.O(1)
.  Runtime of work done inside the recursion given by this formula
n^{logba}
. E.g. O(n^{log21}
) = O(n^{0}
) =O(1)
.
3) Finally, getting the runtime. Based on the comparison of the expressions from the previous steps, find the case it matches.
As we saw in the previous step the work outside and inside the recursion has the same runtime, so we are in case 2.
O(n^{logba} log(n))
Making the substitution we get:
O(n^{log21} log(n))
O(n^{0} log(n))
O(log(n)) 👈 this is running time of binary search
O(n log n)  Linearithmic
Linearithmic time complexity it’s slightly slower than a linear algorithm but still much better than a quadratic algorithm (you will see a graph at the very end of the post).
Mergesort
What’s the best way to sort an array? Before, we proposed a solution using bubble sort that has a time complexity of O(n^2). Can we do better?
We can use an algorithm called mergesort
to make it perform better:
 We are going to divide the array recursively until the elements are two or less.
 We know how to sort 2 items, so we sort them iteratively (base case).
 The final step is merging: we merge in taking one by one from each array such that they are in ascending order.
Here’s the code for merge sort:


As you can see, it has two functions sort
and merge
. Merge is an auxiliary function that runs once through the collection a
and b
, so it’s running time is O(n). Let’s apply the Master Method to find the running time.
Mater Method for Mergesort
We are going to apply the Master Method that we explained above to find the runtime:
1) Let’s find the values of: T(n) = a T(n/b) + f(n)
a
: The number of subproblems is 2 (line 12). So,a = 2
.b
: Each of the subproblems dividesn
in half. So,b = 2
f(n)
: The work done outside the recursion is the functionmerge
, which has a runtime ofO(n)
since it visits all the elements on the given arrays.
Substituting the values:
T(n) = 2 T(n/2) + O(n)
2) Let’s find the work done in the recursion: n^{logba}
.
n^{log22}
n^{1} = n
3) Finally, we can see that recursion runtime from step 2) is O(n) and also the nonrecursion runtime is O(n). So, we have the case 2 : O(n^{logba} log(n))
O(n^{log22} log(n))
O(n^{1} log(n))
O(n log(n)) 👈 this is running time of the merge sort
O(2^n)  Exponential time
Exponential (base 2) running time means that the calculations performed by an algorithm double every time as the input grows.
Subsets of a Set
Finding all distinct subsets of a given set. For instance, let’s do some examples manully to try to come up with an algorithm to solve it:


Did you notice any pattern?
 The first returns have an empty element, and it returns and empty element.
 The second case returns the empty element + the 1st element.
 The 3rd case returns precisely the results of 2nd case + the same array with the 2nd element
b
appended to it.
What if you want to find the subsets of abc
? Well, it would be exactly the subsets of ‘ab’ and again the subsets of ab
with c
appended at the end of each element.
As you noticed, every time the input gets longer the output is twice as long as the previous one. Let’s code it op:


If we run that function for a couple of cases we will get:


As expected, if you plot n
and f(n)
, you will notice that it would be exactly like the function 2^n
. This algorithm has a running time of O(2^n)
.
Note: You should avoid functions with exponential running times (if possible) since they don’t scale well. The time it takes to process the output doubles with every additional input size. But exponential running time is not the worst yet; there are others that go even slower. Let’s see one more example in the next section.
O(n!)  Factorial time
Factorial is the multiplication of all positive integer numbers less than itself. For instance:
5! = 5 x 4 x 3 x 2 x 1 = 120
It grows pretty quickly:
20! = 2,432,902,008,176,640,000
As you might guess, you want to stay away if possible from algorithms that have this running time!
Permutations
Write a function that computes all the different words that can be formed given a string. E.g.


How would you solve that?
A straightforward way will be to check if the string has a length of 1, if so, return that string since you can’t arrange it differently.
For strings with a length bigger than 1, we could use recursion to divide the problem in smaller problems until we get to the length 1 case. We can take out the first character and solve the problem for the remainder of the string until we have a length of 1.


If print out the output, it would be something like this:


I tried with an string with a length of 10. It took around 8 seconds!


I have a little homework for you…
Can you try with a permutation with 11 characters? ;) Comment below what happened to your computer!
All running complexities graphs
We explored the most common algorithms running times with one or two examples each! They should give you an idea how to calculate your running times when developing your projects. Below you can find a chart with a graph of all the time complexities that we covered:
Mind your time complexity!