Complete the following problems. When computing Big-O values, they should be as
ID: 3811784 • Letter: C
Question
Complete the following problems. When computing Big-O values, they should be as tight as possible. This means giving O(2^n!) as the solution to every problem will not receive credit (although technically true). Consider the function f(n) = n^3 + 3n^2 - 2n + 20. In order to prove that f(n) is O(n^3), we need constants c, n_0 > 0 such that f(n) lessthanorequalto cn^3 for every n greaterthanorequalto n_0. Show your work for each part. Suppose we fix c = 3. What is the smallest integer value of n_0 that works? Suppose we fix c = 1.01. Now what is the smallest integer value of n0 to satisfy the inequality? Suppose we want to fix n_0 = 1. Provide some value of c that satisfies the inequality. Provide a value of c such that no matter what value n_0 takes, the inequality cannot be satisfied.Explanation / Answer
a).Here suppose we fix c=3.
Then it becomes as follows:
n3 + 3*n2 - 2*n +20 <= 3*n3
This gives : 2*n3 - 3*n2 + 2*n -20 >= 0
Take inequality equals to 0(then we get smallest value of n0).Then it becomes a cubic equation.
On solving we get one root as 2.597326036618285 and 2 complex roots.
We now get the smallest value n0 = 2.597326036618285.
b.) Simillarly if we put c = 1.01 then the equation is 0.01*n3- 3*n2 + 2*n -20 = 0.
On solving we get one root as 299.3542133601841 and 2 other complex roots.
So n0 = 299.3542133601841.
c) Here suppose we fix n0 =1 then for that value of n we should get n3 + 3*n2 - 2*n +20 is less than or equal to c*n3
which means that c >= 13 + 3*12 - 2*1 +20 means c>=22.
So the smallest value of c would be 22.
d) suppose for c =1 the inequality becomes 3*n2 - 2*n +20 <= 0 which is not true for any value of n0 > 0.