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/