How long will it take to process the company payroll once we complete our planned merger? Should I buy a new payroll program from vendor X or vendor Y? If a particular program is slow, is it badly implemented or is it solving a hard problem?
Questions like these ask us to consider the difficulty of a problem, or the relative efficiency of two or more approaches to solving a problem.
This section and the next introduce the motivation, basic notation, and fundamental techniques of algorithm analysis. In this section we focus on Big O notation a mathematical notation that describes the limiting or asymptotic behavior of a function as the input values become large. In the next section we will use Big O notation to analyze running times of different algorithms using asymptotic algorithm analysis.
Subsection 8.6.1 Big O Notation
Big O is the most frequently used asymptotic notation. It is often used to give an upper bound on the growth of a function, such as the running time of an algorithm. Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same Big O notation. The letter O is used because the growth rate of a function is also referred to as the order of the function
Definition 8.6.1. Big O.
Given functions \(f(x),g(x): \mathbb{R} \rightarrow \mathbb{R}\) with \(g\) non-negative, we say \(f(x)\) is Big O \(g(x)\) or:
\begin{equation*}
f(x) = O(g(x))
\end{equation*}
if and only if there exists a constant \(c \geq 0\) and a \(k\) such that for all \(x \geq k:\)
\begin{equation*}
\lvert f(x) \rvert \leq c g(x)
\end{equation*}
This definition is rather complicated, but the idea is simple: \(f(x) = O(g(x))\) means \(f(x)\) is less than or equal to \(g(x)\text{,}\) except that we’re willing to ignore a constant factor, namely \(c\text{,}\) and to allow exceptions for small \(x\text{,}\) namely, for \(x \leq k\) .
Example 8.6.2. Prove \(10x^2 = O(x^2)\).
If we choose \(c = 10\) and \(k = 0\text{,}\) then \(10x^2 = O(x^2) \) holds because for all \(x \geq 0,\)
\begin{equation*}
\lvert 10x^2 \rvert \leq 10x^2 \text{.}
\end{equation*}
In the following SageMath cell, we plot \(f(x) = 10x^2\text{,}\) \(g(x) = x^2\text{,}\) and \(c\,*\,g(x)\) with \(c = 10\text{.}\) The resulting plot shows that \(f(x)\) (red) never exceeds \(c \,*\, g(x)\) (black dots). That is what we want to show for Big O.
Example 8.6.3. Prove \(x^2 + 100x + 10 = O(x^2)\).
If we take the polynomial \(x^2 + 100x + 10\) and change it so that all of the constant cofficients are multiplied with \(x^2\) we have:
\begin{equation*}
x^2 + 100x^2 + 10x^2 = 111x^2.
\end{equation*}
It must be true that the original polynomial is less than this new equation:
\begin{equation*}
x^2 + 100x + 10 \leq x^2 + 100x^2 + 10x^2, \text{ with } x\geq 1\text{.}
\end{equation*}
Therefore, if we choose \(c = 111\) and \(k = 1\) we have \(x^2 + 100x + 10 = O(x^2)\)
In the following SageMath cell, we plot \(f(x) = x^2 + 100x + 10\text{,}\) \(g(x) = x^2\text{,}\) and \(c\,*\,g(x)\) with \(c = 111\text{.}\) The resulting plot shows that \(f(x)\) (red) never exceeds \(c \, g(x)\) after \(x = 1\) (black dots). That is what we want to show for Big O.
Theorem 8.6.4. Polynomial Big O Theorem.
For any polynomial, the degree of the highest order term will be its Big O
\begin{equation*}
a_k x^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0 = O(x^k)
\end{equation*}
Proof.
Given a polynomial:
\begin{equation*}
a_k x^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0
\end{equation*}
if we replace all of the lower-order \(x\) terms with the highest order \(x^k\) we have:
\begin{equation*}
\begin{array}{c c}\\
a_k x^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0 & \leq a_k x^k + a_{k-1}x^k + \dots + a_1x^k + a_0x^k\\
& = (a_k + a_{k-1} + \dots + a_1 + a_0)x^k\\
\end{array}
\end{equation*}
Therefore,
\begin{equation*}
a_k x^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0 = O(x^k)
\end{equation*}
for \(c = (a_k + a_{k-1} + \dots + a_1 + a_0)\) and \(k \geq 1\text{.}\)
Example 8.6.5. Prove \(6x^4 - 2x^3 + 5 = O(x^4)\).
If we have negative coefficients in a polynomial,
Theorem 8.6.4 still applies because Big O as defined in
Definition 8.6.1 is an upper bound on the
absolute value of
\(f(x)\) and
\(g(x)\) must be non-negative.
Here we take the absolute value of our polynomial \(\lvert 6x^4 - 2x^3 + 5 \rvert\) and multipling all of the constant cofficients by \(x^4\) we have:
\begin{equation*}
\lvert 6x^4 - 2x^4 + 5x^4 \rvert = 6x^4 + \lvert 2x^4 \rvert + 5x^4 = 13x^4.
\end{equation*}
Therefore, we have
\begin{equation*}
\begin{array}{c c}
6x^4 - 2x^3 + 5 & \leq 13x^4 \\
& = O(x^4)
\end{array}
\end{equation*}
With \(c = 13\) and \(k = 1\text{.}\)
We can actually get a closer bound if we realize that the \(- 2x^3\) is only making the outcome of the polynomial smaller:
\begin{equation*}
\lvert 6x^4 - 2x^3 + 5 \rvert < \lvert 6x^4 + 5 \rvert.
\end{equation*}
Therefore, we can also say that \(6x^4 - 2x^3 + 5 = O(x^4)\) for \(c = 11\) and \(k = 1\text{.}\)
We only need to show that one \(c\) and one \(k\) exist to prove Big O. Once they are found, the bound is also true for any larger values of \(c\) and \(k\text{.}\)
In the following SageMath cell, we plot \(f(x) = 6x^4 - 2x^3 + 5\) (red), \(g(x) = x^4\) (blue), and \(c\,*\,g(x)\) with \(c = 13\) (black dots). The resulting plot shows that \(f(x)\) never exceeds \(c \, g(x)\) after \(x = 1\text{.}\) That is what we want to show for Big O.
Example 8.6.6. Big O of \(n!\)
\(n! = n * (n-1) * \dots * 2 * 1\) for \(n \geq 1\text{.}\) There are \(n\) terms total. Since \(n \geq 1 \text{,}\) it must be true that:
\begin{equation*}
n * (n-1) * \dots * 2 * 1 \leq n * n * \dots *n * n = n^n
\end{equation*}
Therefore, \(n! = O(n^n)\) with \(c = 1\) and \(k = 1\text{.}\)
Subsection 8.6.5 Big Theta
Big \(\Theta\) (Theta) combines Big O and Big \(\Omega\) to specify that the growth of a function (or running time of an algorithm) is always equal to some other function plus or minus a constant factor. We take the definitions of both Big O and Big \(\Omega\) to give both an upper and lower bound. It is used to describe the best and worst case running times for an algorithm on a given data size.
Definition 8.6.12. Big \(\Theta\).
Given functions \(f(x),g(x): \mathbb{R} \rightarrow \mathbb{R}\) with \(f,g\) non-negative, we say \(f(x)\) is Big \(\Theta\) (Theta) \(g(x)\) or:
\begin{equation*}
f(x) = \Theta (g(x))
\end{equation*}
if and only if:
\begin{equation*}
f(x) = O(g(x))
\end{equation*}
and
\begin{equation*}
g(x) = O(f(x)).
\end{equation*}
\(f(x) = \Theta (g(x))\) means \(f(x)\) and \(g(x)\) are equal to within a constant factor.
To prove: \(f(x) = \Theta(g(x))\) we must show \(f(x) = O(g(x))\) for some \(c_1\) and \(k_1\) and then flip the equation around and show: \(g(x) = O(f(x))\) for some \(c_2\) and \(k_2\text{.}\)
In the following SageMath cell, we plot \(f(x) = x^4 + 2^x\) (red), this is an addition of two functions with the larger one being the exponential \(2^x\text{,}\) so it should be \(\Theta(2^x)\text{.}\) We show this by using \(g(x) = 2^x\) and plotting both \(c_1\,*\,g(x)\) with \(c_1 = 20\) to show \(f(x) = O(2^x)\) and \(c_2\,*\,g(x)\) with \(c_2 = 1\) to show \(f(x) = \Omega(2^x)\) with black dots. The resulting plot shows that \(f(x)\) is bounded above by \(c_1 \,*\, g(x)\) after \(x \approx 7\) and it is always bounded below by \(c_2 \,*\, g(x)\) . That is what we want to show for Big \(\Theta\text{.}\)
Exercises 8.6.6 Exercises for Section 8.6
1.
Show that \(f(x) = 8x^3 - 5x^2 + 7x + 13 \) is \(\Theta(x^3)\text{.}\) Find \(c_1, c_2, k_1, k_2\text{.}\)
Answer.
for all \(x \geq 1\)
\begin{equation*}
\begin{array}{c c}
8x^3 - 5x^2 + 7x + 13 & \leq 8x^3 + 7x + 13\\
& \leq 8x^3 + 7x^3 + 13x^3\\
& = 28x^3
\end{array}
\end{equation*}
So \(8x^3 - 5x^2 + 7x + 13\) is \(O(x^3)\) with \(c_1 = 28, k_1 = 1\)
\begin{equation*}
\begin{array}{c c}
8x^3 - 5x^2 + 7x + 13 & \geq 8x^3 -5x^2\\
8x^3 - 5x^2 + 7x + 13 & \geq 8x^3 -x^3\\
& x^3 \geq 5x^2 \text{ if } x > 5 \\
& = 7x^3
\end{array}
\end{equation*}
So \(8x^3 - 5x^2 + 7x + 13\) is \(\Omega(x^3)\) with \(c_2 = 7, k_2 = 5\) Therefore \(8x^3 - 5x^2 + 7x + 13\) is \(\Theta(x^3)\text{.}\)
2.
Show that \(f(x) = 10x^2 + x - 22 \) is \(\Theta(x^2)\text{.}\) Find \(c_1, c_2, k_1, k_2\text{.}\)
3.
Show that \(f(x) = x^5 \neq O(x^4)\)
Answer.
\begin{equation*}
\begin{array}{c c}
x^5 & \leq x^4\\
\frac{x^5}{x^4} & \leq \frac{x^4}{x^4}\\
x & \leq 1\\
\end{array}
\end{equation*}
This is false, because by definition of Big O the equation must be true for all values of \(x > k\text{,}\) for some value \(k\text{.}\) Therefore \(x^5 \neq O(x^4)\)
4.
For each pair of functions below, determine whether \(f(x) = O(g(x))\) and whether \(g(x) = O(f(x))\text{.}\) If one function is Big O of the other, give values for \(c\) and \(k\text{.}\)
\(\displaystyle f(x) = x^2, g(x) = 3x.\)
\(\displaystyle f(x) = \frac{3x - 7}{x+4}, g(x) = 4.\)
\(\displaystyle f(x) = 2^x, g(x) = 2^{\frac{x}{2}}.\)
\(\displaystyle f(x) = \log (n!), g(x) = \log (n^n).\)
\(\displaystyle f(x) = x^{10}, g(x) = 10^x.\)
5.
Determine whether each of the functions: \(\log(3n + 2)\) and \(\log(n^3 + 1)\) is \(O(\log n)\) by finding a valid \(c\) and \(k\) for each, or showing they do not exist.
Answer.
\begin{equation*}
\begin{array}{c c}
\log(3n + 2) & \leq \log(3n + n), \forall n > 2\\
& = \log(4n)\\
& = \log 4 + \log n\\
& \leq \log n + \log n, \text{ if } n > 4.\\
& = 2 \log n.
\end{array}
\end{equation*}
Therefore \(\log(3n + 2)\) is \(O(\log n)\) with \(c = 2, k = 4\text{.}\)
\begin{equation*}
\begin{array}{c c}
\log(n^3 + 1) & \leq \log(n^3 + n^3), \forall n > 1\\
& = \log(2n^3)\\
& = \log 2 + \log n^3\\
& = \log 2 + 3\log n\\
& \leq 4 \log n, \text{ if } n > 2.
\end{array}
\end{equation*}
Therefore \(\log(n^3 + 1)\) is \(O(\log n)\) with \(c = 4, k = 2\text{.}\)
6.
Arrange these functions into a sequence from smallest to largest Big O
\(\displaystyle n\log n\)
\(\displaystyle 2^{100} n\)
\(\displaystyle n!\)
\(\displaystyle 2^{2^{100}}\)
\(\displaystyle 2^{2^{n}}\)
\(\displaystyle 2^{n}\)
\(\displaystyle 3^n\)
\(\displaystyle n2^{n}\)
\(\displaystyle 2n\)
\(\displaystyle 3n\)
\(\displaystyle n^2\)
\(\displaystyle n^3\)
\(\displaystyle \log (n!)\)
