TWO PROOFS THAT EXAMPLE ALGORITHM #2's TIME COMPLEXITY is O(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 + 4n^2 + 5n^2 = 12n^2 when n >= 1

    Therefore, T(n) is O(n^2) for c = 12 and n_0 = 1

Proof #2

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

    Suppose we set c = 4:

               4n + 5 <= n^2
                    5 <= n^2 - 4n    
                    5 <= n(n - 4)      => Requires n >= 5    

    Therefore, T(n) is O(n^2) for c = 4 and n_0 = 5
        


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

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

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

which can never be true, as the value of n is arbitrary but c is a constant.