8.1: Big O
( \newcommand{\kernel}{\mathrm{null}\,}\)
Big O
The idea of Big O is to characterize functions according to their growth rates. The O refers to the order of a function. In computer science, Big O is used to classify algorithms for their running time or space requirements.
Notice in the figure below that f(x)>g(x) right before x=1. However, for x>1, we see that g(x)>f(x). In the long run (namely after x>1) g(x) overtakes f(x).
We say "f is of order at most g" or "f(x) is Big O of g(x)" .
We write: f(x)=O(g(x)).
In our definition of Big O notation, there are certain parameters.
- We use x greater than a certain initial value, n; in the diagram above, n=1.
- We use absolute value for both functions.
- We use k as a constant multiplied by the function inside the O.
Definition: Big O Notation
f(x)=O(g(x)).
if and only if there exist real numbers k,n with k>0,n≥0 such that
|f(x)|≤k|g(x)|∀x>n.
Example 8.1.1
Take this statement and express it in Big O notation: |7x5+4x3+x|≤14|x5| for x>1.
- Solution
-
(7x5+4x3+x) is O(x5)
Comparing orders of common functions
A constant function, such as f(x)=6 does not grow at all. Logarithmic functions grow very slowly. Here is a list of some common functions in increasing order of growth rates.
constant function, logarithmic function, polynomial function, exponential function
Example 8.1.2
Put these functions in order of increasing growth rates:
log6x,x5,2x,x2,log15x,100x4,64x+1000,x5log6x,5x,6
- Solution
-
6,log6x,log15x,64x+1000,x2,100x4,x5,x5log6x,2x,5x
Proofs
We will be using the Triangle Inequality Theorem which is |x+y| ≤|x|+|y|.
Example 8.1.3
Prove: 4x3−11x2+3x−2=O(x3)
- Proof
-
Choose n=1, i.e. x≥1.
|4x3−11x2+3x−2|≤|4x3|+|−11x2|+|3x|+|−2| by the Triangle Inequality Theorem
=4x3+11x2+3x+2 applying absolute value; note: x is positive
≤4x3+11x3+3x3+2x3 since x is positive and greater than 1
=20x3
=20|x3| since x is positive and greater than 1
Thus for all x≥1, |4x3−11x2+3x−2|≤20|x3|
Therefore, using n=1 and k=20, 4x3−11x2+3x−2=O(x3) by the definition of Big O.
Summary and Review
- Big O is used to compare the growth rates of functions.
- Be sure to understand the examples here.
Exercises
exercise 8.1.1
True or False?
(a) 11x3=O(87x2)
(b) x13=O(3x)
(c) −2x=O(58log35x)
- Answer
-
(a) false
(b) true
(c) false
Exercise 8.1.2
True or False?
(a) 4x3+12x2+36=O(x3)
(b) .01x5=O(48x4)
(c) 4x=O(x7)
(d) 3xlog2x=O(25x)
Exercise 8.1.3
True or False?
(a) 23lnx=O(3x)
(b) 7x5=O(x5)
(c) x5=O(7x5)
- Answer
-
all true
Exercise 8.1.4
Prove: 2x5+3x4−x3+5x=O(x5)
Example 8.1.5
Put these functions in order of increasing growth rates:
x7,6x,78x2,x2logx,1000x,7,log11x
- Answer
-
7,log11x,1000x,78x2,x2logx,x7,6x
Exercise 8.1.6
Take this statement and express it in Big O notation: |2x4−5x3+x2−5|≤13|x4| for x>1.