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