4.1: Big-O Notation

\( \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}\)

1. If \(1<a<b\), then \(x^a\) is \(O(x^b)\) but \(x^b\) is not \(O(x^a)\).
2. If \(b>1\), then \(\log_b(x)\) is \(O(x)\) but \(x\) is not \(O(\log_b(x))\).
3. If \(b>1\) and \(a\) is positive, then \(x^a\) is \(O(b^x)\) but \(b^x\) is not \(O(x^a)\)
4. 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.