TWO PROOFS THAT EXAMPLE ALGORITHM #2's TIME COMPLEXITY is OMEGA(n^2):

Need to show T(n) = 3n^2 + 4n + 5 >= cn^2 for all n >= n_0 
for some constants c, n_0.

Proof #1

        3n^2 + 4n + 5 >= 3n^2 when n >= 1

    Therefore, T(n) is OMEGA(n^2) for c = 3 and n_0 = 1

Proof #2

        3n^2 + 4n + 5 >= cn^2
               4n + 5 >= (c - 3)n^2    => Holds when c <= 3

    Therefore, T(n) is OMEGA(n^2) for c <= 3 and n_0 = 1
        


A PROOF THAT EXAMPLE ALGORITHM #2's TIME COMPLEXITY IS NOT OMEGA(n^3)

Proof by contradiction: Suppose T(n) is OMEGA(n^3). If so, by definition, we
an show T(n) = 3n^2 + 4n + 5 >= cn^3 for all n >= n_0 for some constants c, 
n_0. However,

        3n^2 + 4n + 5 >= cn^3
         3/n + 4/n^2 + 5/n^3 >= c

which cannot be true, as the left-hand size asymptotically goes to 0
as n goes to infinity and hence cannot be greater than any constant c > 0
for a sufficiently large value of n.