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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.