<< Chapter < Page Chapter >> Page >

Big - omega and big - theta

Big-oh concerns with the "less than or equal to" relation between functions for large values of the variable. It is also possible to consider the "greater than or equal to" relation and "equal to" relation in a similar way. Big-Omega is for the former and big-theta is for the latter.

Definition (big-omega): Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be Ω(g(x)) , which is read as f(x) is big-omega of g(x) , if there are constants C and n0 such that

     | f(x) | ≥C | g(x) |

whenever x>n0 .

Definition (big-theta): Let f and g be functions from the set of integers (or the set of real numbers) to the set of real numbers. Then f(x) is said to be θ( g(x) ) , which is read as f(x) is big-theta of g(x) , if f(x) is O( g(x) ), and Ω( g(x) ) . We also say that f(x) is of order g(x) .

For example,   3x2 - 3x - 5  is Ω( x2 ) , because   3x2 - 3x - 5 ≥x2   for integers x>2   (C = 1 , n0 = 2 ) .

Hence by Theorem 1 it is θ( x2) .

In general, we have the following theorem:

Theorem 4: an xn + ... + a1 x + a0   is   θ( xn )   for any real numbers an , ..., a0 and any nonnegative number n .

Little - oh and little - omega

If f(x) is O( g(x) ), but not θ( g(x) ) , then f(x) is said to be o( g(x) ) , and it is read as f(x) is little-oh of g(x) . Similarly for little-omega (ω).

For example   x is   o(x2 ) ,   x2 is   o(2x ) ,   2x is   o(x ! ) , etc.

Calculation of big – oh

Basic knowledge of limits and derivatives of functions from calculus is necessary here. Big-oh relationships between functions can be tested using limit of function as follows:

Let f(x) and g(x) be functions from a set of real numbers to a set of real numbers.

Then

1.     If   lim x f ( x ) / g ( x ) = 0 size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \) =0} {} , then  f(x) is o( g(x) ) . Note that if  f(x) is o( g(x) ), then f(x) is O( g(x) ).

2.     If  lim x f ( x ) / g ( x ) = size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \) = infinity } {} , then   g(x) is o( f(x) ) .

3.     If   0 < lim x f ( x ) / g ( x ) < size 12{0<{"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \)<infinity } {} , then   f(x) is θ( g(x) ) .

4.     If   lim x f ( x ) / g ( x ) < size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \)<infinity } {} , then   f(x) is O( g(x) ) .

For example,

lim x size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {} (4x3 + 3x2 + 5)/(x4 – 3x3 – 5x -4) 

= lim x size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {} ( 4/x + 3/x2 + 5/x4 )/(1 - 3/x - 5/x3 - 4/x4 ) = 0 .

Hence

( 4x3 + 3x2 + 5 )   is   o(x4 - 3x3 - 5x - 4 ),  

or equivalently,   (x4 - 3x3 - 5x - 4 ) is   ω(4x3 + 3x2 + 5 ) .

Let us see why these rules hold. Here we give a proof for 4. Others can be proven similarly.

Proof: Suppose   lim x f ( x ) / g ( x ) = C 1 < size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } f \( x \) /g \( x \) =C rSub { size 8{1} }<infinity } {} .

By the definition of limit this means that

∀ε>0, ∃n0 such that   |f(x)/g(x) – C1|<ε whenever x>n0

Hence –ε<f(x)/g(x) – C1<ε

Hence –ε +C1<f(x)/g(x)<ε +C1

In particular f(x)/g(x)<ε +C1

Hence f(x)<(ε +C1)g(x)

Let C = ε +C1 , then f(x)<Cg(x) whenever x>n0 .

Since we are interested in non-negative functions f and g, this means that   |f(x) | ≤C | g(x) |

Hence   f(x) = O( g(x) ) .

L'hospital (l'hôpital)'s rule

lim x size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {} f(x)/g(x) is not always easy to calculate. For example take lim x size 12{ {"lim"} cSub { size 8{x rightarrow infinity } } } {} x2/3x. Since both x2 and 3x go to ∞ as x goes to ∞ and there is no apparent factor common to both, the calculation of the limit is not immediate. One tool we may be able to use in such cases is L'Hospital's Rule, which is given as a theorem below.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Discrete structures. OpenStax CNX. Jan 23, 2008 Download for free at http://cnx.org/content/col10513/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Discrete structures' conversation and receive update notifications?

Ask