Big O, Omega, and Sigma

Date: 09/19/2001 at 20:47:27
From: Jeremy
Subject: Big O, Omega, and Sigma

Hello,

I think that I understand Big O and Omega notation (At large n, one is 
better/faster than another, and vice versa), but I cannot understand 
how something can be both Big O and Omega (aka Big Theta). I know that 
this specifies the order, but I can't get it. A general explanation of 
O/Omega/Theta (or a link to such) would be most helpful.

Jeremy

Date: 09/20/2001 at 15:38:41
From: Doctor Douglas
Subject: Re: Big O, Omega, and Sigma

Hi Jeremy,

Thanks for writing to Dr. Math.  

Below are the definitions of big-oh, big-omega, and big-theta from
the following Web page:

  Growth of Functions - Computer Science, Old Dominion University
  http://www.cs.odu.edu/~toida/nerzic/content/function/growth.html      

Definition (big-oh): 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 O( g(x) ), which is read as f(x) is big-oh of g(x), if and 
only if there are constants C and n0 such that | f(x) | <= C | g(x) | 
whenever x > n0. 

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 Omega( 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 Theta( g(x) ), which is read as f(x) is big-theta 
of g(x), if f(x) is O( g(x) ), and Omega( g(x) ). We also say that 
f(x) is of order g(x).

Here is an example of how a function can be both big-o and big-omega:

  Consider the function f(x) = 5x^3 + x^2 + 1/(1+x^2). Without going 
  through the complete details on the proof, it's apparent that
  f is O(x^3), since f(x) <= 7x^3 for x >= 1 (bounded above by Cx^3)
  f is Omega(x^3), since f(x) >= 5x^3 for x >= 1 (bounded below by 
  Dx^3) Hence f is both O(x^3) and Omega(x^3), and thereby f is 
  Theta(x^3) also.

The above Web page also has more information on big-o, big-omega, and 
big-theta, as well as little-o and little-omega.

I hope this helps.  

- Doctor Douglas, The Math Forum
  http://mathforum.org/dr.math/