I am a beginner and taking an online algorithm course, and when I referred to a book, I found the following question.
- 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.
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$$