Complete the following problems. When computing Big-O/Big-Q values, they should
ID: 3585824 • Letter: C
Question
Complete the following problems. When computing Big-O/Big-Q values, they should be as tight as possible. This means giving 0(2") as the solution to every problem will not receive credit (although technically true, it would be meaningless) Consider the function f(n) = 3n3-39n2 + 360n + 20. In order to prove that f(n) is (n*), we need constants c,no0 such that f(n) 2 cn3 for every n 2 no. Show your work for each part. Work should include any steps you performed to solve the problem (e.g., derivations, arithmetic, "I entered this into Wolfram Alpha"...). (3 points each for 12 total) 1. Suppose we fix c = 2.25. what is the smallest integer value of no that works? Suppose we fix c-3. Now what is the smallest integer value of no to satisfy the inequality? Suppose we want to fix no-1. Provide some value of c that satisfies the inequality. Provide a value of c such that no matter what value no takes, the inequality cannot be satisfied. a. b. C. d.Explanation / Answer
a. 13 is the minimum n0 where the inequality is specified. I found this using a graph. I graphed both the equations and found the intersection point. It is 12.something, hence the integer is 13.
b.10 by the same method
c. 343, but hit and trial on the graph by fixing the interserction point at 1.
d. -300 is a value for which there doesn't exists a value of n0 for which the inequality can be satisfied. Again this was done by graphs but this time I graph the subtration of the first derivative of two equations. This gives me a graph where after and including 1 the graph is always increasing. It decreases between 0 and 1 but since it is increasing after that the inequality is not satisfied.