DISCRETE MATHEMATICS

Question

Show that x² + 5x + 11 is O(x²) 

Answer 1

If we consider this polynomial  , f(x) = x2 + 5x + 11  

Then clearly for all x>1 , 5x + 11 < x²

which means f(x) <= x² + x²

and

therefore f(x) <= 2x² for all x > 1.

Therefore, the polynomial f(x) is O(x^2), which is an upper bound .

Comments

@Kapil. I think your line of reasoning isnt appropriate. I think it should be like this:

Lets assume that x² + 5x +11 is O(x²).

Thus, x² + 5x +11 <= c_1.(x²)   where c₁ is some positive constant (as per big-O def.)

Thus, 5x +11 <= c_1.(x²)

Now, there should be constriant on both c₁ and value of x to decide if the above statement is true. For c₁=1 and from x>=7, above statement holds true. There can be other values as well.

If we want for x>1, we can have c₁ =1000 or something like this.

---

Kapil sir i am also waiting eagerly for the reply.

---

here c1 will be equal to 7 as far my teacher teachings are concerned and my mind is concerned?

correct me if i am wrong?

---

and x should be greater than equal to 1 ?