The big oh notation introduced in the preceding section
is an asymptotic *upper bound*.
In this section, we introduce a similar notation
for characterizing the asymptotic behavior of a function,
but in this case it is a *lower bound*.

Definition (Omega)Consider a functionf(n) which is non-negative for all integers . We say that ``f(n) is omegag(n),'' which we write , if there exists an integer and a constantc>0 such that for all integers , .

The definition of omega is almost identical to that of big oh. The only difference is in the comparison--for big oh it is ; for omega, it is . All of the same conventions and caveats apply to omega as they do to big oh.

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.