Summary
Given the number of ways an algorithm could be implemented, there is a need for a way to compare algorithms to choose the “best one”. The “best” algorithm depends on what you need to optimize – do you need it to complete as quickly as possible or use the least amount of space? Both of these questions can be considered in terms of “how many more resources are needed as the input size gets very large?”. In this way, the growth rate of the algorithm can be measured and compared.
Big-O is standardized notation that represents the upper limit of the growth rate of the algorithms. If your runtime function, T(N), is O(N2), then T(N) is guaranteed to grow no faster than N2, within some constant factor and for values of N larger than some particular value.
To make Big-O runtimes as useful as possible, the Big-O bound should be as tight as possible. That is, if T(N) is O(N2), then T(N) is also O(N3) and O(2n), etc. However, you want to represent your algorithm in the best possible light and provide the most accurate estimation, so you wouldn’t say T(N) is O(N3) or O(2n) (because those are really very terrible runtimes).
Furthermore, the runtimes used to compare algorithms represent the worst case or average case of the algorithm. The average runtime is often hard to precisely define, so worst case scenarios are often used.
Keep this in mind when using runtimes to evaluate different algorithms. For example, if your data set is very small, an otherwise “inefficient” algorithm may actually perform better than the more efficient algorithm. The runtimes also represent the worst case scenarios. If you have information about your data, the algorithm may never encounter the worst case. Still, Big-O provides a useful snapshot and starting point for evaluating the efficiency of a given algorithm.
