Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Functions

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/