Chapter 3 - Comparing Orders of Growth Using Limits

Computing the limit of the ratio of two functions is another way to classify the growth of a function.

f(n)/g(n) What f(n) is in terms of O, Θ, Ω, o, and ω   o O Θ Ω ω 0 f(n) ∈ o(g(n))         c   f(n) ∈ O(g(n)) f(n) ∈ Θ(g(n)) f(n) ∈ Ω(g(n))   ∞         f(n) ∈ ω(g(n))

Definition of O, Θ, Ω, o, and ω by limits

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

ω  f(n) / g(n) = ∞

O  f(n) / g(n) = c for some 0 ≤ c < ∞

o  f(n) / g(n) = 0

Θ f(n) / g(n) = c for some 0 < c < ∞

Question 3.18.0 - Examining the limit definitions:

1. What is implied by f(n) / g(n) = ∞?
   
   
2. What is implied by f(n) / g(n) = c = 0 in the definition of O?
   
   
3. What values do O and o have in common?
   
   
4. What is implied by f(n) / g(n) = c = ∞ in the definition of Ω?
   
   
5. What values do ω and Ω have in common?
   
   
6. What other values are shared by bounds?
   
   
7. Does f(n) = Ω(g(n)) and f(n) = O(g(n)) imply f(n) = Θ(g(n))?
   
   
8. Does f(n) = Θ(g(n)) imply f(n) = Ω(g(n)) and f(n) = O(g(n))?
   
   
9. Why does it make sense to say that Θ is asymptotically tight?

Graph showing (n²/2-2n) / n² → constant

Definition of O, Θ, Ω, o, and ω by limits

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

ω  f(n) / g(n) = ∞

O  f(n) / g(n) = c for some 0 ≤ c < ∞

o  f(n) / g(n) = 0

Θ f(n) / g(n) = c for some 0 < c < ∞

o  f(n) / g(n) = 0 

• Means f(n) has a smaller order of growth than g(n)
  
• f(n) ∈ O(g(n))
  
• Even though g(n) is not an asymptotically tight upper bound for f(n), by definition of Big-O, we can still state that f(n) ∈ O(g(n))

Question 3.18.1     Why?

ω  f(n) / g(n) = ∞    

• Means f(n) has a larger order of growth than g(n)
  
• f(n) ∈ ω(g(n))
  
• Even though g(n) is not an asymptotically tight lower bound for f(n), by definition of Ω, we can still state that f(n) ∈ Ω(g(n))

Question 3.18.2     Why?

 

Example

n^1.999= o(n²)

n^2.001= ω(n²)

Graphs of f(n) / g(n) for n^2.001/n² = ω(n²)

and f(n) / g(n) for  n^1.999= o(n²)

Question 3.19

1. Does 0 ≤ f(n) < cg(n) appear correct for n^1.999= o(n²)?  f(n) / g(n) = 0 
   
2. Does 0 ≤ cg(n) < f(n) appear correct for n^2.001= ω(n²)?  f(n) / g(n) = ∞
   

Definition of O, Θ, Ω, o, and ω by limits

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

ω  f(n) / g(n) = ∞

O  f(n) / g(n) = c for some 0 ≤ c < ∞

o  f(n) / g(n) = 0

Θ f(n) / g(n) = c for some 0 < c < ∞

O, Θ, Ω  When f(n) / g(n) = c

• Means f(n) has the same order of growth as g(n) within a constant factor

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

O  f(n) / g(n) = c for some 0 ≤ c < ∞

Θ f(n) / g(n) = c for some 0 < c < ∞

Example -  n²/2-2n = Θ(n²)  with c₁=1/4, c₂=1/2 and n₀=8

1/4n² ≤ n²/2-2n ≤ 1/2n² for n ≥ 8

Graph showing (n²/2-2n) / n² → constant

Question 3.20

1. In (n²/2-2n) / n² → constant - What is the constant? 
   
2. Does the limit appear to agree with the graph?
   
   
3. c₁n² ≤ n²/2-2n ≤ c₂n² with c₁=1/4, c₂=1/2 and n₀=8.

   What about c₁=1/3, c₂=2 and n₀=8?
   
   

4. n²/2-2n = Θ(n²), is it also O(n²) and Ω(n²)?

Example

Compare  f(n) and g(n) to determine the asymptotic notation for f(n) in terms of g(n), where f(n) and g(n) are:

• f(n) = 1/2 * x * (x + 1)
• g(n) = x²

f(n) / g(n)  =  1/2 (x² + x) / x²  =  1/2 (1 + 1/x)  =  1/2

The limit is a constant c = 1/2, f(n) and g(n) have the same order of growth, so f(n) ∈ Θ(g(n))

Definition of O, Θ, Ω, o, and ω by limits

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

ω  f(n) / g(n) = ∞

O  f(n) / g(n) = c for some 0 ≤ c < ∞

o  f(n) / g(n) = 0

Θ f(n) / g(n) = c for some 0 < c < ∞

Example:

Compare f(n) and g(n):

• f(n) = 1000x² 
• g(n) = 5x³ 

f(n) / g(n) =  1000x² / 5x³  =  200 1/x  =  0

The limit is zero, f(n) has smaller order of growth than g(n),

f(n) ∈ o(g(n)) and f(n) ∈ O(g(n))

Example:

Compare f(n) and g(n):

• f(n) = 5x³ 
• g(n) = 1000x² 

f(n) / g(n) =  5x³  / 1000x²  =  x / 200  = ∞ 

The limit is ∞, f(n) grows faster than g(n),

f(n) ∈ Ω(g(n)) and f(n) ∈ Ω(g(n))

Definition of O, Θ, Ω, o, and ω by limits

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

ω  f(n) / g(n) = ∞

O  f(n) / g(n) = c for some 0 ≤ c < ∞

o  f(n) / g(n) = 0

Θ f(n) / g(n) = c for some 0 < c < ∞

Example:

Compare f(n) and g(n):

• f(n) = x²/2-2x  
• g(n) = x² 

f(n) / g(n) =  x²/2-2x  / x²  =  1/2 - 1/x  = 1/2 

The limit is a constant c = 1/2, so f(n) and g(n) have the same order of growth,

f(n) ∈ Θ(g(n))

 

Example

Compare f(n) and g(n):

• f(n) =  x²
• g(n) = x²/2-2x 

f(n) / g(n) =    x² / (x²/2-2x)  =  2x/(x-4)  = 2 

Note that x > 4 since f(n) / g(n) discontinuous, undefined at x=4, that is: 2*4/(4-4). 

Definition of O, Θ, Ω, o, and ω by limits

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

ω  f(n) / g(n) = ∞

O  f(n) / g(n) = c for some 0 ≤ c < ∞

o  f(n) / g(n) = 0

Θ f(n) / g(n) = c for some 0 < c < ∞

Question 3.21 - Use limits to classify f(x).

1. • f(x) =  x², g(x) = x³

2. • f(x) =  x³, g(x) = x²

3. • f(x) =  2x², g(x) = x²

Exponentials

Example - For all real constants a and b such that a > 1,

n^b/aⁿ = 0

The graph at right is of  n²/2ⁿ

Question 3.22 - Classify the example? O, Θ, Ω, ω, o?

Definition of O, Θ, Ω, o, and ω by limits

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

ω  f(n) / g(n) = ∞

O  f(n) / g(n) = c for some 0 ≤ c < ∞

o  f(n) / g(n) = 0

Θ f(n) / g(n) = c for some 0 < c < ∞

Logarithms

Logarithm functions apply only to the next term in the formula, so that lg n + k means (lg n) + k, and not lg(n + k).

In the expression log_b a:

If we hold b constant, then the expression is strictly increasing as a increases.
If we hold a constant, then the expression is strictly decreasing as b increases.

log2 a

logb 2 log2 4096 = 12 log4 4096 = 6 log16 4096 = 3

Changing the base of a logarithm from one constant to another only changes the value by a constant factor, so we usually don't worry about logarithm bases in asymptotic notation.

Convention is to use lg within asymptotic notation, unless the base actually matters.

Just as polynomials grow more slowly than exponentials, logarithms grow more slowly than polynomials.

n^b/aⁿ = 0

To show for logarithms, substitute lg n for n and 2^a for constant a:

(lg n)^b/(2^a)^{lg n} = lg^b n/(2^{lg n})^a

                                = lg^b n/n^a = 0

Note that  lg^b n = (lg n)^b

implying (lg n)^b = o(n^a) and O(n^a)

 

The graph at right is of  lg n²/n²

Definition of O, Θ, Ω, o, and ω by limits

Ω  f(n) / g(n) = c for some 0 < c ≤ ∞

ω  f(n) / g(n) = ∞

O  f(n) / g(n) = c for some 0 ≤ c < ∞

o  f(n) / g(n) = 0

Θ f(n) / g(n) = c for some 0 < c < ∞

 

Factorials

1. n! = o(nⁿ) by inspection. Each of the n terms of n! is at most n. n!=1*2*3*...*n-1*n < n*n*n*...*n*n
   
   
2. n! = ω(2ⁿ) by inspection. Question 3.23 - Show by a comparison similar to 1 above.
   
   
3. lg n! = Θ(n lg n).

   Note that lg MN = lg M + lg N

   lg 1*2*3*4*5 = lg 1 + lg 2 + lg 3 + lg 4 + lg 5

4. n! = ω(2ⁿ) by limits using Stirling's formula for n! where

   e = 2.71828182845904523536028747135266249775724709369995...

    

   ω  f(n) / g(n) = ∞