2.2: Big O notation

Last updated
Save as PDF

Page ID: 12730

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

All constant time algorithms belong to a set called \( O(1) \). So another way to say that an algorithm is constant time is to say that it is in \( O(1) \). Similarly, all linear algorithms belong to \( O(n) \), and all quadratic algorithms belong to \( O(n^2) \). This way of classifying algorithms is called “big O notation”.

Note

I am providing a casual definition of big O notation. For a more mathematical treatment, see thinkdast.com/bigo.

This notation provides a convenient way to write general rules about how algorithms behave when we compose them. For example, if you perform a linear time algorithm followed by a constant algorithm, the total run time is linear. Using \( \in \) to mean “is a member of”:

If \( f \in O(n) \) and \( g \in O(1) \), \( f + g \in O(n) \).

If you perform two linear operations, the total is still linear:

If \( f \in O(n) \) and \( g \in O(n) \), \( f + g \in O(n) \)

In fact, if you perform a linear operation any number of times, k, the total is linear, as long as k is a constant that does not depend on n.

If \( f \in O(n) \) and k is a constant, \( kf \in O(n) \).
But if you perform a linear operation n times, the result is quadratic:

If \( f \in O(n) \), \( nf \in O(n^2) \).

In general, we only care about the largest exponent of n. So if the total number of operations is \( 2n+1 \), it belongs to O(n). The leading constant, 2, and the additive term, 1, are not important for this kind of analysis. Similarly, \( n^2 + 100n + 1000 \) is in \( O(n^2) \). Don’t be distracted by the big numbers!

“Order of growth” is another name for the same idea. An order of growth is a set of algorithms whose run times are in the same big O category; for example, all linear algorithms belong to the same order of growth because their run times are in \( O(n) \).

In this context, an “order” is a group, like the Order of the Knights of the Round Table, which is a group of knights, not a way of lining them up. So you can imagine the Order of Linear Algorithms as a set of brave, chivalrous, and particularly efficient algorithms.