Data Structures, Algorithms, & Applications in C++
Chapter 3, Exercise 13
If f(n) = Omega(g(n)),
then there exist a positive c and an
n0
such that g(n)/f(n) <= c for all
n >= n0. Hence, the limit of
g(n)/f(n) as n goes to
infinity is <= c. Next, suppose that
the limit of g(n)/f(n) as n
goes to infinity is <= c. From
this it follows that there is
an n0 such that g(n)
<= max{1, c} * f(n) for all n >= n0.
This proves Theorem 3.4. Theorems 3.2 and 3.4 together imply Theorem 3.6.