4.1: Big-O Notation
- Page ID
- 18515
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)
\( \def\d{\displaystyle}\)
\( \newcommand{\f}[1]{\mathfrak #1}\)
\( \newcommand{\s}[1]{\mathscr #1}\)
\( \def\N{\mathbb N}\)
\( \def\B{\mathbf{B}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\Z{\mathbb Z}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\Q{\mathbb Q}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\R{\mathbb R}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\C{\mathbb C}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\F{\mathbb F}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\A{\mathbb A}\)
\( \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\)
\( \def\X{\mathbb X}\)
\( \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\)
\( \def\E{\mathbb E}\)
\( \def\O{\mathbb O}\)
\( \def\U{\mathcal U}\)
\( \def\pow{\mathcal P}\)
\( \def\inv{^{-1}}\)
\( \def\nrml{\triangleleft}\)
\( \def\st{:}\)
\( \def\~{\widetilde}\)
\( \def\rem{\mathcal R}\)
\( \def\sigalg{$\sigma$-algebra }\)
\( \def\Gal{\mbox{Gal}}\)
\( \def\iff{\leftrightarrow}\)
\( \def\Iff{\Leftrightarrow}\)
\( \def\land{\wedge}\)
\( \def\And{\bigwedge}\)
\( \def\entry{\entry}\)
\( \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\)
\( \def\Vee{\bigvee}\)
\( \def\VVee{\d\Vee\mkern-18mu\Vee}\)
\( \def\imp{\rightarrow}\)
\( \def\Imp{\Rightarrow}\)
\( \def\Fi{\Leftarrow}\)
\( \def\var{\mbox{var}}\)
\( \def\Th{\mbox{Th}}\)
\( \def\entry{\entry}\)
\( \def\sat{\mbox{Sat}}\)
\( \def\con{\mbox{Con}}\)
\( \def\iffmodels{\bmodels\models}\)
\( \def\dbland{\bigwedge \!\!\bigwedge}\)
\( \def\dom{\mbox{dom}}\)
\( \def\rng{\mbox{range}}\)
\( \def\isom{\cong}\)
\(\DeclareMathOperator{\wgt}{wgt}\)
\( \newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}\)
\( \newcommand{\va}[1]{\vtx{above}{#1}}\)
\( \newcommand{\vb}[1]{\vtx{below}{#1}}\)
\( \newcommand{\vr}[1]{\vtx{right}{#1}}\)
\( \newcommand{\vl}[1]{\vtx{left}{#1}}\)
\( \renewcommand{\v}{\vtx{above}{}}\)
\( \def\circleA{(-.5,0) circle (1)}\)
\( \def\circleAlabel{(-1.5,.6) node[above]{$A$}}\)
\( \def\circleB{(.5,0) circle (1)}\)
\( \def\circleBlabel{(1.5,.6) node[above]{$B$}}\)
\( \def\circleC{(0,-1) circle (1)}\)
\( \def\circleClabel{(.5,-2) node[right]{$C$}}\)
\( \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\)
\( \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\)
\( \def\ansfilename{practice-answers}\)
\( \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\)
\( \renewcommand{\bar}{\overline}\)
\( \newcommand{\card}[1]{\left| #1 \right|}\)
\( \newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\( \newcommand{\lt}{<}\)
\( \newcommand{\gt}{>}\)
\( \newcommand{\amp}{&}\)
\( \newcommand{\hexbox}[3]{
\def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}
\def\y{-\r*#1-sin{30}*\r*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\)
\(\renewcommand{\bar}{\overline}\)
\(\newcommand{\card}[1]{\left| #1 \right|}\)
\(\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}\)
\(\newcommand{\lt}{<}\)
\(\newcommand{\gt}{>}\)
\(\newcommand{\amp}{&}\)
Investigate!
Show that the following functions of \(n\) are ranked in order from least to greatest eventual growth.
\(1, \log_2 n, n, n\log_2 n, n^2, 2^n, n!, n^n\)
For what integer values of \(n\) does a function in the list above surpass (or equal) the previous one?
Big-O notation is commonly used to describe the growth of functions and, as we will see in subsequent sections, in estimating the number of operations an algorithm requires.
Definition: Big-o notation
Let \(f\) and \(g\) be real-valued functions (with domain \(\mathbb{R}\) or \(\mathbb{N}\)) and assume that \(g\) is eventually positive. We say that \(f(x)\) is \(O(g(x))\) if there are constants \(M\) and \(k\) so that
\(|f(x)|\le Mg(x)\)
for all \(x> k\). We read this as "\(f\) is big-O of \(g\)" and sometimes it is written as \(f(x)=O(g(x))\).
To show that one function is big-O of another, we must produce the constants \(M\) and \(k\).
Example \(\PageIndex{1}\)
Show that \(f(x)=x^2+3x-2\) is \(O(x^3)\).
Solution
We notice that as long as \(x> 1\), \(x^2\le x^3\) and \(3x-2\le x^3\). Therefore, when \(x> 1\), we have that \(|f(x)|=x^2+3x-2\le 2x^3\). So we choose \(k=1\) and \(M=2\). There are infinitely many other choices for pairs \(k,M\) that would work as well.
Exercise \(\PageIndex{2}\)
Suppose \(f(x)=x^2+2x+2\) and \(g(x)=x^2\). Prove that \(f(x)\) is \(O(g(x))\) and \(g(x)\) is \(O(f(x))\)
- Hint
-
For the first part, use \(k=2\) and \(M=3\). For the second, try \(k=0\) and \(M=1\).
If two functions \(f\) and \(g\) are both big-O of the other one, we say that \(f\) and \(g\) have the same order.
We can also use the definition to show that a function is not big-O of another.
Exercise \(\PageIndex{3}\)
Prove that \(f(x)=3x^5\) is not \(O(x^4)\).
- Hint
-
Assume that a \(k\) and \(M\) exist and then find a contradiction.
In fact, we can prove a statement involving polynomials in general.
Theorem \(\PageIndex{4}\)
Let \(p(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0\) where the \(a_i\) are real numbers with \(a_n\neq 0\). Then \(p(x)\) is \(O(x^m)\) if and only if \(m\ge n\). [In particular, \(p(x)\) is of order \(x^n\).]
- Proof Idea
-
First assume that \(m\ge n\) and use \(k=1\). (Think about what \(M\) should be.) Then assume \(m<n\) and show that it is not possible for \(p(x)\) to be \(O(x^m)\) similarly to how we did in the prior exercise.
So far, we haven't considered any examples of functions with domain \(\mathbb{N}\).
Example \(\PageIndex{5}\)
Suppose \(f(n)=1^2+2^2+\cdots +n^2\). Show that \(f(n)\) is \(O(n^3)\).
Solution
Notice that \(f(n)=1^2+2^2+\cdots+n^2\le n^2+n^2+\cdots +n^2=n^3\). Using \(k=M=1\) we see that \(f(n)\) is \(O(n^3)\).
Some results for commonly-used functions are given below.
Theorem \(\PageIndex{6}\)
- If \(1<a<b\), then \(x^a\) is \(O(x^b)\) but \(x^b\) is not \(O(x^a)\).
- If \(b>1\), then \(\log_b(x)\) is \(O(x)\) but \(x\) is not \(O(\log_b(x))\).
- If \(b>1\) and \(a\) is positive, then \(x^a\) is \(O(b^x)\) but \(b^x\) is not \(O(x^a)\)
- If \(1<a<b\), then \(a^x\) is \(O(b^x)\) but \(b^x\) is not \(O(a^x)\).
You should be able to prove all of these.
Theorem \(\PageIndex{7}\)
Suppose that \(f_1(x)\) is \(O(g_1(x))\) and \(f_2(x)\) is \(O(g_2(x))\). Then \((f_1+f_2)(x)\) is \(O(\max(|g_1(x)|,|g_2(x)|)\) and \((f_1f_2)(x)\) is \(O(g_1(x)g_2(x))\).
- Proof
-
We will prove the second result here; the proof of the first is similar. We know that there exist constants \(M_1,M_2,k_1,k_2\) so that \(|f_1(x)|\le M_1|g_1(x)| \) for \(x> k_1\) and \(|f_2(x)|\le M_2|g_2(x)|\) for \(x> k_2\). Then, as long as \(x\) is bigger than both \(k_1\) and \(k_2\) we have that \(|f_1(x)f_2(x)|\le |f_1(x)||f_1(x)|\le M_1|g_1(x)| M_2|g_2(x)|\le M_1M_2|g_1(x)g_2(x)|\). In particular we use \(M=M_1M_2\) and \(k=\max(k_1,k_2)\).
Now apply these prior results.
Exercise \(\PageIndex{8}\)
Show that \(h(x)=(x+1)^2\log(x^4-3)+2x^3\) is \(O(x^3)\).
There are a few other definitions provided below, also related to growth of functions. Big-omega notation is used to when discussing lower bounds in much the same way that big-O is for upper bounds.
Definition: Big-\(\Omega\) Notation
Let \(f\) and \(g\) be real-valued functions (with domain \(\mathbb{R}\) or \(\mathbb{N}\)). We say that \(f(x)\) is \(\Omega(g(x))\) if there are constants \(M\) and \(k\) so that
\(|f(x)|\ge M|g(x)|\)
for all \(x> k\). We read this as "\(f\) is big-omega of \(g\)".
Definition: BIG-\(\Theta\) Notation
Let \(f\) and \(g\) be real-valued functions (with domain \(\mathbb{R}\) or \(\mathbb{N}\)). We say that \(f(x)\) is \(\Theta(g(x))\) if \(f(x)\) is both \(\Omega(g(x))\) and \(O(g(x))\). We read this as "\(f\) is big-theta of \(g\)" and that \(f\) and \(g\) have the same order.