In a nutshell
Big O is a notation that describes how an algorithm’s time and space requirements will change in proportion to the input size. Just like you might use the Richter scale to indicate the strength of a earthquake, you can use Big O notation to indicate the time/space complexity of an algorithm.
Why is the Big O notation useful?
By giving an insight into how an algorithm’s time and space requirements will change in proportion to the input size, Big O can help you pick the most suitable algorithm. For example:
- Pick the algorithm that executes fastest, especially when working with large datasets.
- Pick the algorithm that requires the least memory space. Sometimes, it’s more important for the algorithm to use a small amount of memory than that it executes fast (e.g., on a small embedded device that needs to run some code very infrequently).
- Pick the algorithm that executes in the most consistent timeframe. Sometimes, consistency is more important than speed. So it’s useful to know which algorithms are more consistent than others.
Big O notations
There are a few common Big O labels that describe the time and memory requirements of an algorithm: