Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

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)).

bigO.png 

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,n0 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: 4x311x2+3x2=O(x3)  

Proof

Choose n=1, i.e. x1.
|4x311x2+3x2||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 x1, |4x311x2+3x2|20|x3|

Therefore, using n=1 and k=204x311x2+3x2=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+3x4x3+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:  |2x45x3+x25|13|x4|  for x>1.


This page titled 8.1: Big O is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?