
# 4.1: Big-O Notation

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\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 ParseError: EOF expected (click for details) Callstack: at (Template:MathJaxLevin), /content/body/div/p[1]/span, line 1, column 11 at template() at (Courses/Saint_Mary's_College,_Notre_Dame,_IN/SMC:_MATH_339_-_Discrete_Mathematics_(Rohatgi)/Text/4:_Algorithms/4.1:_Big-O_Notation), /content/body/p[1]/span, line 1, column 22 $$
$$\renewcommand{\bar}{\overline}$$
$$\newcommand{\card}[1]{\left| #1 \right|}$$
$$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$$
$$\newcommand{\lt}{&lt;}$$
$$\newcommand{\gt}{&gt;}$$
$$\newcommand{\amp}{&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 M|g(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.