Complete the following problems. When computing Big-O values, they should be as

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.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.