In this article, I will focus on explaining the big O notation that you can find with any algorithm. This notation is important to understand when you are dealing with algorithms. You need to understand the impact of using your selected algorithm in term of run time and this is what the big O notation stand for.
As I am not coming from computer science degree, I always found it hard to understand what those notation meant. When I found out, I felt that I should have known that before, like one of the first thing to learn. Thanks the big O notation, you can better understand why some of the algorithms are more famous than others and which one you should prefer for your problem.
Global Explanation
The Big O notation is a mathematical notation that gives you the time require for an algorithm to run through a data set. Each algorithm that you will encounter should have a big O notation. Technically, it is calculating the relation between the run-time and space requirement of an algorithm with the growth of the data set.
What you would like to achieve is to take the most efficient algorithm for your purpose and therefore, knowing the run-time associated with it is important. In computer science, it is always a matter of trade-off, when 2 algorithms are doing the same thing but one is faster, it means that it is doing things differently and thus you may want to know what exactly you are missing by using the fastest one (or not). However, if the result is what you wanted from the start, don’t bother too much with it (except if you are a mathematician).
There are some information that are usually given with the algorithm big O notation but I will try to give some example of big O notation in the following paragraph and you should see how those different notation can be interpreted.
The constant : O(1)
When you encounter the O(1) notation on an algorithm, it means that the algorithm runs at a constant speed. It doesn’t have any correlation with the number of elements or the dataset amount. It doesn’t mean that this is fast but that it will always run at the same speed.
A good example of that in python is the way dictionary are returning a value for a key. This method is O(1).
Overall, big O notation don’t usually display constants. As explained before, they are showing relation between the run-time and the data set size. Constant may be important for very small number but when your data set is increasing drastically (millions of entries), it shouldn’t matter anymore.
Linear relationship : O(n)
This notation is indicating that the algorithm run-time will grow proportionally to one element, generally your data set. In python, this kind of algorithm are the one you are most likely to use when you are searching for an item in a list.
The good example of this kind of algorithm is : Linear Seach.
Logarithm relationship : O(log n)
This notation is indicating that the algorithm run-time is not growing as fast as the size of the correlated element, here again it is usually the data set. This kind of algorithm is very interesting because it has a lot of potential when you encounter very large data set. The increase of elements in your data set doesn’t impact greatly the run time. This is very efficient.
The good example of an algorithm that is displaying this feature : Binary search.
Quadratic relationship : O(n2)
This kind of function is very expensive to run and you want to avoid this as much as possible, when you have a choice. The time spent to run the algorithm is doubling for every item.
The good example of quadratic function is : Selection sort
Linearithmic relationship : O(n log(n))
This relationship is increasing somehow proportionally with the size of the data set, however, the logarithm part of it make it quite optimized. It is faster than a pure linear relationship but slower than a logarithmic functions.
A good example of algorithm running with this performance : Quick Sort.
I hope this article was helpful and you get the idea of measuring performance between 2 algorithms using this notation. As you will go down the path of machine learning, this kind of side-knowledge, which are implied between Computer Science engineers can be disturbing if you don’t have the code.
Hopefully that article will give you the key to go further and start optimizing your algorithmic usage. If you want to go deeper into that notation or discover other notations, you can always find interesting article on wikipedia : https://en.wikipedia.org/wiki/Big_O_notation