Prove each of the following statements by applying the definition of Big-O. That is, derive an inequality (show your work) and clearly identify the c, n0 constants you derive as per the definition of Big-O.

(a) 3n = O(n) (b) 500 n = O(n)

(b) 500 n = O(n)

(c) n 2 + 2n + 1 = O(n 2 )

(d) 2048n + 1234 = O(n 2 )

(e) n log (32n) = O(n log (n)))

(f) 12n 3 + 50n 2 12n 60 = O(n 3 )

(g) n2 n = O(3n )

(h) log (n!) = O(n log n)