Section 8.6 Growth of Functions
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
This definition is rather complicated, but the idea is simple: means is less than or equal to except that we’re willing to ignore a constant factor, namely and to allow exceptions for small namely, for .
Example 8.6.2. Prove .
In the following SageMath cell, we plot and with The resulting plot shows that (red) never exceeds (black dots). That is what we want to show for Big O.
xxxxxxxxxx
f(x) = 10*x^2
g(x) = x^2
c = 10
p1 = plot(f, (x,0,5), color="red" , legend_label='f(x)', thickness='2')
p2 = plot(g, (x,0,5), color="blue", legend_label='g(x)', thickness='2')
p3 = plot(c*g, (x,0,5), color="black", linestyle="dotted", legend_label='10*g(x)', thickness='3')
p1+ p2 + p3
Example 8.6.3. Prove .
If we take the polynomial and change it so that all of the constant cofficients are multiplied with we have:
It must be true that the original polynomial is less than this new equation:
In the following SageMath cell, we plot and with The resulting plot shows that (red) never exceeds after (black dots). That is what we want to show for Big O.
xxxxxxxxxx
f(x) = (x^2 + 100*x + 10)
g(x) = x^2
c = 111
p1 = plot(f, (x,0,3), color="red" , legend_label='f(x)', thickness='2')
p2 = plot(g, (x,0,3), color="blue", legend_label='g(x)', thickness='2')
p3 = plot(c*g, (x,0,3), color="black", linestyle="dotted", legend_label='c*g(x)', thickness='3')
p1+ p2 + p3
Theorem 8.6.4. Polynomial Big O Theorem.
For any polynomial, the degree of the highest order term will be its Big O
Proof.
Given a polynomial:
if we replace all of the lower-order terms with the highest order we have:
Therefore,
for and
Example 8.6.5. Prove .
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 and must be non-negative.
Here we take the absolute value of our polynomial and multipling all of the constant cofficients by we have:
Therefore, we have
We can actually get a closer bound if we realize that the is only making the outcome of the polynomial smaller:
We only need to show that one and one exist to prove Big O. Once they are found, the bound is also true for any larger values of and
In the following SageMath cell, we plot (red), (blue), and with (black dots). The resulting plot shows that never exceeds after That is what we want to show for Big O.
xxxxxxxxxx
f(x) = (6*x^4 - 2*x^3 + 5)
g(x) = x^4
c = 13
p1 = plot(f, (x,0,3), color="red" , legend_label='f(x)', thickness='2')
p2 = plot(g, (x,0,3), color="blue", legend_label='g(x)', thickness='2')
p3 = plot(c*g, (x,0,3), color="black", linestyle="dotted", legend_label='c*g(x)', thickness='3')
p1+ p2 + p3
Example 8.6.6. Big O of
Subsection 8.6.2 Big O For Common Functional Forms
In Section 9.3 we will be using several functions to analyze the running time of algorithms. The most commonly encountered functions are shown in the Figure 8.6.7 below.

1
creativecommons.org/licenses/by-sa/4.0
In addition to polynomials, we have the following Big O estimates:
- Any power of
is Big O any larger power of powers greater than 1: - A logarithm of
to a power is Big O any power of for log bases greater than 1: - Any power of
is Big O an exponential in - Any exponential is Big O an exponential of a larger constant:
Notation | Name | Example |
Constant time | No looping; Determining if a binary number is even or odd; Calculating |
|
Logarithmic time | Loops where |
|
Finding an item in a sorted array with a BinarySearch. | ||
Linear time | One loop over all |
|
Linearithmic time | Algorithms that divide |
|
Fastest possible comparison sort; HeapSort and MergeSort | ||
Quadratic time | Two nested loops both over |
|
Simple sorting algorithms, such as BubbleSort, SelectionSort, and InsertionSort | ||
Polynomial time |
|
|
|
Exponential time | Recursive algorithms that make two or more recursive calls each time; |
Determining if two logical statements are equivalent using a truth table ( |
||
Factorial time | Solving the travelling salesman problem via brute-force search; enumerating all partitions of a set | |
|
Resulting value of |
|
Subsection 8.6.3 Big O For Combinations of Functions
The Big O of multiple functions can be combined. If we have a complex function, we can break it down into simpler parts then find the Big O of the simpler functions and combine them.
- If two functions are added together, their Big O is the Big O of the larger one.
- If
and
- If two functions are multiplied together, their Big O is the product of the Big O of both.
- If
and
Example 8.6.9. Big O of .
Here we have two functions multiplied together: and We can calculate the Big O of both separately and combine them.
For the first one Theorem 8.6.4 applies so we have For there are no powers or constants so the Big O is just
Multiplying:
Example 8.6.10. Big O of .
Here we have two functions added together: and We must calculate the Big O of both separately and decide which is largest.
For the first one Theorem 8.6.4 applies so we have For this is an exponential in so the Big O is just the function itself: Looking at Figure 8.6.7 we can see that grows much faster than the polynomial therefore
Subsection 8.6.4 Big Omega
This is almost the same definition as Big O, except that Big (Omega) gives a lower bound on the growth of a function or running time of an algorithm. It is used to describe the best case running time for an algorithm on a given data size.
Definition 8.6.11. Big .
to mean
To prove: we just flip the equation around into Big O form: and find a and where is greater than or equal to
Subsection 8.6.5 Big Theta
Big (Theta) combines Big O and Big 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 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 .
if and only if:
and
In the following SageMath cell, we plot (red), this is an addition of two functions with the larger one being the exponential so it should be We show this by using and plotting both with to show and with to show with black dots. The resulting plot shows that is bounded above by after and it is always bounded below by . That is what we want to show for Big
xxxxxxxxxx
f(x) = (x^4 + 2^x)
g(x) = 2^x
c1 = 20
c2 = 1
p1 = plot(f, (x,0,10), color="red" , legend_label='f(x)', thickness='2')
p2 = plot(c1*g, (x,0,10), color="black", linestyle="dotted", legend_label='20 * g(x)', thickness='3')
p3 = plot(c2*g, (x,0,10), color="black", linestyle="dotted", legend_label='1 * g(x)', thickness='3')
p1+ p2 + p3
Exercises 8.6.6 Exercises for Section 8.6
1.
Answer.
for all
So is with
So is with Therefore is
2.
3.
Show that
Answer.
This is false, because by definition of Big O the equation must be true for all values of for some value Therefore
4.
For each pair of functions below, determine whether and whether If one function is Big O of the other, give values for and
5.
Determine whether each of the functions: and is by finding a valid and for each, or showing they do not exist.
Answer.
Therefore is with
Therefore is with
6.
Arrange these functions into a sequence from smallest to largest Big O