# 2.2: Big O notation

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\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.

This page titled 2.2: Big O notation is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press) .