Big O of rational function using the definition

Question

I want to prove that $\dfrac{3x^3+2x^2+x+1}{4x^2+1}$ is $O(x)$.

I am having problem in finding $c$ and $k$ and proving that it is big O, since the function involves a fraction.

How would I go about doing this?

Answer 1

Rewrite $\frac{3x^3+2x^2+x+1}{4x^2+1} = \frac{3}{4}x \cdot \frac{12x^3+8x^2+4x+4}{12x^3+3x} = \frac{3}{4}x (1 + \frac{8x^2+x+4}{12x^3+3x})$.

Clearly, the limit of $f(x) = \frac{8x^2+x+4}{12x^3+3x}$ for $x \to +\infty$ is $0$ and hence, for any constant $c'>0$, there is a constant $x'_0$ such that $f(x) \le c'$ for all $x \ge x'_0$. Pick your favorite constant $c'$, for example $c'=1$. You want to figure out any value of $x'_0$ for which $f(x) \le 1$ or, equivalently:

$$ 12x^3+2x - 4 \ge 8x^2. $$

This is clearly true for $x'_0=1$. Indeed, if $x \ge 1$: $$ 12x^3+2x - 4 > 12x^2 - 4 \ge 8x^2 + 4x^2 - 4 \ge 8x^2. $$

Going back to the original formula we can conclude that, for every $x \ge 1$, $$ \frac{3}{4} x \cdot \left(1 + \frac{8x^2+x+4}{12x^3+3x} \right) \le \frac{3}{4} x \cdot (1 + 1) = \frac{3}{2} x. $$

Which satisfies the definition of $O(x)$ once you pick $c = \frac{3}{2}$ and $x_0=1$.