0.7 Discrete structures function  (Page 4/5)

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   $\underset{x\to \infty }{\text{lim}}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  $\underset{x\to \infty }{\text{lim}}f(x)/g(x)=\infty$ , then   g(x) is o( f(x) ) .

3.     If   , then   f(x) is θ( g(x) ) .

4.     If   , then   f(x) is O( g(x) ) .

For example,

$\underset{x\to \infty }{\text{lim}}$ (4x3 + 3x2 + 5)/(x4 – 3x3 – 5x -4) 

= $\underset{x\to \infty }{\text{lim}}$ ( 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   .

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

$\underset{x\to \infty }{\text{lim}}$ f(x)/g(x) is not always easy to calculate. For example take $\underset{x\to \infty }{\text{lim}}$ 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.