Search by title or category tag
What is runtime complexity? It’s how we describe the performance of an alogrithm.
If you only take away one thing from this article let it be this: If your code contains two nested loops iterating over the same collection, you need to refactor. We would need to switch from an iterative solution to a recursive solution.
There are times when a recursive solution gives us an expontential runtime complexity such as the infamous fibonacci problem. In that example we need to combine recursion with memoisation if we dont want to initialise the fn with values. For now though lets just focus on the basics:
We have six major types of runtime complexity
- Constant time
- Logarithimic time
- Linear time
- Quasilinear time
- Quadratic time
- Expontential time
Firstly ill give you an quick explanation on each, then we’ll run through how to identify which runtime complexity your algorithm is and finally ill show you a visual graph of different types to help tie it all together.
Constant time - O(1)
No matter how many elements we’re working with, the algorithm/operation/function will always take the same amount of time.
Logarithimic time - O(log (n))
You get this if doubling the number of elements you are iterating over doesnt double the amount of work. Always assume that searching operations are log(n).
Linear time - O(n)
Iterating through a collection of data. If you see a for loop spanning from ‘0’ to array.length you probably have ‘n’ or linear time. A common example of this is the reduce() fn.
Quasilinear time - O(n*log(n))
You have this if doubling the number of elements you are iterating over doesnt double the amount of work. Always assume that any sorting operations is n*log(n)
Quadratic time - O(n^2)
Every element in a collection has to be compared to every other element. ‘The handshake problem’
Exponential time - O(2^n)
If you add a ‘single’ element to a collection, the processing power required doubles.
How to identify which runtime complexity your algorithim is?
- Iterating with a simple loop through a single collection? - probably O(n)
- Iterating over two different collections with seperate for loops? - O(n+m)
- Two nested for loops iterating over the same collection? - O(n^2)
- Two nested for loops iterating over different collections? - O(n*m)
- Sorting - O(n*log(n))
- Searching a sorted array? - O(log(n))
What does this look like on a graph?
