Advantages and Disadvantages of the Big-O Notation

Have a look at the pros and cons of the big-O notation.

We'll cover the following

Advantages

Using the big-OO notation to report algorithm running times has several advantages:

  • In many cases, computer scientists mainly care about how the running time grows with the input size—the big-OO notation clarifies the growth rate.

  • The big-OO notation simplifies the formulas for the running time:

    • O(n2)O(n^2) vs. 3n2+5n+23n^2+5n+2.
    • O(n)O(n) vs. n+log⁡2n+7n+\log_2n +7.
    • O(nlog⁡n)O(n\log n) vs. 4nlog⁡2n+54n\log_2n+5. In particular, log⁡2n\log_2n, log⁡3n\log_3n, and log⁡an\log_an differ by constant multipliers, so we don’t need to specify the base of the logarithm in the big-OO notation.
  • With the big-OO notation, we no longer need to worry about things like how fast the computer is, what the memory hierarchy looks like, or what compiler we used. Although these things will have a big impact on the final running time, that impact will generally only be a constant multiple.

These advantages come with some disadvantages.

Disadvantages

The big-OO notation loses some information since it ignores constant multipliers and additive terms. If we have two algorithms, and one of them is a hundred times faster, they still have the same estimate of the running time in the big-OO notation. But, in practice, if we want to make things fast, a factor of 100 is a big deal.

Nevertheless, the big-OO notation is very useful, and we will use it throughout this course.