Big O Notation

Definition of Big O
f(x) is O(g(x) if there are constants C and k such that

|f(x)| <=  C |g(x)| whenever x>k

This is read as f(x) is big-oh of g(x).

In English, this means that the function f(x) grows no faster than g(x) as  x gets larger. A function that is O(x3) grows faster than one that is O(x2). What we would like is to develop algorithms that have the smallest O values.
Name(in order of difficulty) Big O Example
Constant 1 f(x) = 5
Logarithmic log n f(x) = 3 (log x)
Linear n f(x) = 3x + 8
n log n n log n f(x) = x (log x)
Polynomial xn f(x) = 3x3 + 2x2 + x + 3     O(x3)
Exponential bn f(x) =  3x     O( 3x )     
Factorial n! f(x) = x!

 

Function

Derivation
For polynomial functions, the big O is O(xn) where n is the exponent on the lead term (i.e. the degree of the polynomial). Linear functions are a special case where the degree is 1. Constant functions are a special case where there is no x term.  If f(x) = anxn + an-1xn-1 ...  a1x + a0

If f(x) is of degree n,   O(xn)
Suppose that we have a function f(n)=n! where n is the factorial function (4!=4*3*2*1).
n!  = 1*2*3....n
n! <= n*n*n...n = nn
Then if f(n) = n!, O(nn )
(Taking the logs of both sides)
log (n!)  <= log(nn) = n (log n)
If f(n) = log n!, O(n log n)
Suppose that we have an exponential function say, bn.

 

 Start with bn
then n < bn
log n < log bn = n log b
Let log b be a constant, c,
then log n < cn
If f(n)=log n, then O(n)

 

Definition 1 states:
|f(x)| <= C |g(x)| for some C whenever x>k means O(g(x)).

Let's take f(x) log (n**j) and show that it is O(log x).

|(log x**j)| = |j* log (x)|<= C |(log x)| = |(log xC)|. By definition 1, we can choose any C. Any C>|j|>=0 makes this true. (Since we can't take the log of a negative number, we have x>k or x>=0. In addition, we need j>=0 for the inequality to be true.) Thus  log x  is O(log x) by definition 1.

While (log x)is O(n) as stated in the book, it is also O(log x). Since O(log x) is the smaller of the two, O(log x) is the least upper bound and "official" O. See page 82 for a discussion of this.

 

Name Definition Informally Example
Addition of O If f1(x) is O(g1(x)) and  f2(x) is O(g2(x)), then (f1+f2)(x) = O(max(g1(x),g2(x))) If terms are added, the O is the O of the largest O of the terms. If f(x)=x2+ log x, then
O(x2) since the O(x2) is greater than O(log x).
Multiplication of O If  f1(x) is O(g1(x)) and  f2(x) is O(g2(x)), then (f1*f2)(x) = O(g1(x)*g2(x))  If terms are multiplied, the O is the product of the multiplied terms.  If f(x)=x2 * log x,
O(x2 log x)
Comprehensive Example
Let f(x) = (x3 + x2 log x) (log x + 1) + (17 log x +19) (x3+2)

Let's start with the first half, (x3 + x2 log x) (log x + 1) and break this down to
    (x3 + x2 log x)  The largest term between   O(x3) and O(x2 log x) is O(x3)
  and
    (log n + 1) The largest term is log n.
Since this is multiplication, we have O(x3* log x) for this part.

Now let's take the second half, (17 log x +19) (x3+2) and break this down to
    (17 log x +19) The largest  O is O(log x)
   and
   (x3+2) The largest O is O(x3)
Since this is multiplication, we have O(x3 * log x) 

Now let's add the two halves.
Taking the larger of the O's of the two halves,  O(x3 * log x)    and O(x3 * log x)  , we have

O(x3 * log x)  which is the O for f(x). This tells us how the function f(x) grows.

Hint: Break the problem into parts where you can use either the sum rule or the multiplication rule. Then divide the problem into subproblems in which you can again apply the rules An so on. This type of problem solving, in which you break the problem into subproblems, is similar to a tree search

 

 

   You are the visitor to this site.

Return to Main Page