-1

I am a beginner and taking an online algorithm course, and when I referred to a book, I found the following question.

  1. Given that $f(x) = 2x^2 + 5x +3$ and $g(x) = 2x^3 +x -100$, prove $f(x) = O(g(x))$

I know that to prove $f(x) = O(g(x))$, I have to show that there are some positive constants $c$ and $x_{min}$ for which if $x\ge x_{min}$ then $f(x)\le c \cdot g(x)$.

I tried the following:

Let c = 4 and x = 5.
I want to prove that $2x^2 + 5x + 3 \le c(2x^3 + x - 100)$.
I tried to solve the left side as follows:
If $x \ge 1$, then $x^2 \le x^3$ and $5x \le 5x^3$ and $3 \le 3x^3$.
So $2x^2 + 5x + 3 \le 2x^3 + 5x^3 + 3x^3$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;= 10x^3$

My question is can I ignore the $-100$ of $g(x)$ and compare it with $10x^3$ for some value of $c$?

Thanks for any explanation.

Matt
  • 9,223
Jonatan
  • 13
  • Welcome to Maths SX! I suppose this is when $x\to\infty$? – Bernard Sep 07 '18 at 22:07
  • @Bernard yes as x grows faster. – Jonatan Sep 07 '18 at 22:10
  • The purpose of this exercise is to help you understand how to prove a simple example of "big-O" notation, so no, you cannot ignore the -100. You should not "try to solve the left side" -- instead, you should try to show that when $x$ is large enough, the inequality will be true. So you should use $x>5$, not $x=5$. Setting $c=4$ and subtracting the left from the right, can you show that $0<8x^3−2x^2-x−403$ when $x>5$? Hint: If you rewrite it as $0<(2x^3-2x^2)+(x^3-x)+(5x^3-403)$, then you can see that each term on the right is positive. – Matt Sep 13 '18 at 21:18

1 Answers1

0

Hint:

Use equivalence: $$f(x)\sim_\infty 2x^2,\qquad g(x)\sim_\infty 2x^3,\quad\text{ so }\quad\frac{f(x)}{g(x)}\sim_\infty\dots$$

Bernard
  • 175,478
  • Thanks for the explanation but if what if I am asked to prove f(x) = O(g(x))? Do I need to ignore the x-100 (every term except the fastest growing term)? – Jonatan Sep 07 '18 at 22:23
  • This proves a stronger result: $f(x)=o\bigl(g(x)\bigr)$. I think you're supposed to know a polynomial is asymptotically equivalent to its leading term. So we don't have to care for the other terms. – Bernard Sep 07 '18 at 22:26