Skip to main content
\(\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}}\)
Mathematics LibreTexts

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

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