Exercise 3

This project is intended to give you some simple, concrete experience with the formal definitions of O and .Let f(n) =n3. For each of the functions given below, formally prove, directly from the definition, that f(g). Each of your 6 separate proofs must clearlystateNandcas in the definition of O() and must clearly show the algebra proving your inequalities. Make sure that you have some reason for choosing N and c, rather than just guessing and bluffing that the corresponding inequality is true (Ill be more skeptical of your inequalities if you havent pickedNandcsensibly).

a. g(n) = 1000n^3

b. g(n) =n^3+ 1000n^2

c. g(n) =n^31000n^2 (assume n1000 for this to be a legitimate function for ourpurposes)