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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search