Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

An Asymptotic Lower Bound-Omega

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 function f(n) which is non-negative for all integers tex2html_wrap_inline59063. We say that ``f(n) is omega g(n),'' which we write tex2html_wrap_inline59919, if there exists an integer tex2html_wrap_inline59043 and a constant c>0 such that for all integers tex2html_wrap_inline59075, tex2html_wrap_inline59927.

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




next up previous contents index

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