---------------   Example 1:  -------------------------

Claim:  t(n) = 5 n log n + (n + 3)^2 - 8 n   is  O( n^2)

Proof:

We want to find positive constants  c, n0 such that,
for all n > n0,

   5 n log n + (n + 3)^2 - 8 n  < c n^2

But

    5 n log n + (n + 3)^2 - 8 n 
<   5 n * n   + (n + n)^2,         for n >= 3
=   9 n^2

So take n0 = 3,  c = 9

(There are other possibilities for n0 and c.)

-----------------  Example 2:  -----------------------

Claim:     t(n) =  n - 3 log n - 5  is Omega(n)

Proof:

Observe that t(n) <= n  for all n >= 1.   So, we will need c
to be less than 1.    Try c = 1/2.  

We now want to show there exists n0 such that,
for all n  >= n0,

   n - 3 log n - 5 >=  n/2 

or  n/2 >= 3 log n + 5.

How can we show this?  Notice that 

 3 log n + 5 log n  >=  3 log n + 5,    for n >= 1. 

So,  let's find the values of n for which 

 n/2 >= 3 log n + 5 log n,  or equivalently,

   n   >= 2* 8 log n.   

We notice that  n / log n  is an increasing function, and 
the inequality certainly holds if n > 2^10.   (It holds for
smaller n too, but we don't care.)

So, we take n0 = 2^10, c = 1/2.

----------------  Example 3:  ------------------------------

Claim:   Show t(n) =  sqrt( n^2 - 5 n)  is Omega(n)

Proof:   We want to show there are positive constants c and n0 such
        that, for all n > n0,  

               sqrt(n^2 - 5n) > cn.

Squaring both sides gives:

               n^2 - 5n  >  c^2 n^2

    <--->     (1 - c^2) n^2 >  5n  

    <--->     (1 - c^2) n >  5

where "<----->"  means if and only if, i.e. equivalent inequalities.

Try c = 0.5.  This  gives the inequality:   3/4 * n > 5, 

which is true for any n > 5* (4/3) = 6.666...  So take n0 = 7, c = 0.5.