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
_____________________________________________

Functions O(k) and Omega(k)


Date: 01/20/2001 at 04:45:52
From: David Ganor
Subject: The functions O(k) and Omega(k)

I read some articles about paging algorithms in computer science and I 
have encountered two similar expressions: O(k), read, I think, as 
"Order of k", and Omega(k). Could you please clarify the meaning of 
each function and the difference between them? I think it has to do 
with polynomials and of a way to compare two or more algorithms.

Thank you,
David Ganor


Date: 01/20/2001 at 20:57:37
From: Doctor Rob
Subject: Re: The functions O(k) and Omega(k)

Thanks for writing to Ask Dr. Math, David.

Let f and g be functions from the natural numbers to the real numbers.

     f(n) = O(g(n))

means that there exist constants N > 0 and C > 0 such that for all
n > N:

     |f(n)| <= C*|g(n)|

In English, from some point (n = N + 1) on, the ratio |f(n)/g(n)| is 
bounded above by some constant C. In other words, g grows at least as 
fast as f as n approaches infinity.

On the other hand,

     f(n) = OMEGA(g(n))

means that there exists constants N > 0 and C > 0 such that for all 
n > N,

     |f(n)| >= C*|g(n)|

In English, from some point (n = N + 1) on, the ratio |f(n)/g(n)| is 
bounded below by some constant C. In other words, f grows at least as 
fast as g as n approaches infinity.

- Doctor Rob, 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/