Determine appropriate $c$ and $x_0$ for Big-O proofs.

Question

"Prove that $f(x)$ is $O(x^2)$:"

$$f(x) = \frac{x^4+2x-7}{2x^2-x-1}$$

Let $c=10$ (addition of coefficients of the numerator less the addition of coefficients of the denominator), and $x_0 = 1$ (the lowest coefficient among all elements in the function).

$$\frac{x^4+2x-7}{2x^2-x-1} \leq \frac{x^4+2x^4-7x^4}{2x^4-x^4-x^4} \leq 10x^2$$

Am I going on the right track? For any $x \geq 1$, the second fraction becomes troublesome, as you then get a division by zero. I'm not sure how to approach these questions if someone could assist me.

Answer 1

I will try to give you a more intuitive approach.

Theoretical Approach

The basic idea is the following: when $x$ get sufficiently large, the highest order term dominates over all the rest.

$x^4 + 2x - 7$ will eventually look like $x^4$.

$2x^2 -x - 1$ will eventually look like $2x^2$.

So

$\dfrac{x^4 + 2x - 7}{2x^2-x-1}$ will eventually look like $\dfrac{x^4}{2x^2} = \dfrac{1}{2}x^2$.

This is one way of seeing why your function should be $O(x^2)$.

Now, what should be $c$? You actually do NOT want to use $1/2$. This is because you want something that is definitely larger than $\frac{x^4 + 2x - 7}{2x^2-x-1}$. So you definitely want $c$ to be something bigger than $1/2$.

Theoretically speaking, you can choose $c$ to be any number bigger than $c$, and theoretically, $x_0$ exists. This is because when $x$ is very big, $\frac{x^4 + 2x - 7}{2x^2-x-1}$ is very close to $\dfrac{1}{2}x^2$, which will be smaller than $cx^2$.

More Practical Approach

You have a fraction. If you want an upper bound for a fraction, you need

1. An upper bound for the numerator. (Bigger numerator means bigger value $\dfrac{2}{2} < \dfrac{4}{2}$)
2. A lower bound for the denominator. (Smaller denominator means bigger value $\dfrac{2}{2} < \dfrac{2}{1}$)

Note from our theoretical approach that our top should be bounded by $x^4$, and the bottom should be bounded by $x^2$.

Easiest thing to do for the top: bound each term by $x^4$, the higher order term. It works precisely because higher order terms dominate eventually.

$x^4 \le x^4$, always.

$2x \le x^4$, when say $x > 2$. (To be more exact, this happens precisely when $2 \le x^3$, or $\sqrt[3]{2} \le x$. But for $O$ proofs this kind of precision is unnecessary.)

$-7 \le x^4$, always.

So, $x^4 + 2x - 7 \le x^4 + x^4 + x^4 = 3x^4$.

Now, what about the denominator?

I need something that will be eventually smaller than $2x^2 - x - 1$. Note from what I said earlier, that we want to use something like $x^2$. So $n x^2$ is good, for any $n$ less than 2. In fact, to make things easy, let's choose $n=1$.

The question now becomes: When will $2x^2 - x - 1 > x^2$?

$2x^2 - x - 1 > x^2$ becomes

$x^2 - x - 1 > 0 $.

$y = x^2 - x - 1$ is a parabola, and you just need to figure out some positive number $x$ where this parabola becomes positive.

How about $x = 10$? $(10^2) - 10 - 1 > 0$. And if you plug in a larger value for $x$, then it'll certainly be bigger.

Note: What Tim did in his answer was to find the precise point at which $2x^2 - x - 1 = x^2$. This gives you a much more precise $x_0$. But this isn't necessary for $O$ proofs.

So when $x>10$, we have both:

1. $x^4 + 2x - 7 \le x^4 + x^4 + x^4 = 3x^4$.
2. $2x^2 - x - 1 > x^2$.

And so

$\dfrac{x^4 + 2x - 7}{2x^2-x-1} < \dfrac{3x^4}{x^2} = 3x^2$

So my solution uses $c=3$ with $x_0 = 10$.

Answer 2

Find the limit

$$ \lim_{n\to \infty} \frac{f(x)}{x^2}=\dots\,, $$

and use the result

$$f=O(g)\quad \rm{iff} \quad \limsup_{x \to \infty}\frac{|f(x)|}{|g(x)|} =c,$$

where $c$ is finite.

Added: If you want to use the method you mentioned in your comment, then try to use the long division of polynomials.

Answer 3

Note that

$$\frac{x^4 + 2x -7}{2x^2 - x - 1} \leq \frac{x^4 + 2x^4 -7}{2x^2 - x - 1} \leq \frac{3x^4}{2x^2 - x - 1} \leq \frac{3x^4}{x^2} = 3x^2.$$

The last inequality holds true when $$2x^2 - x - 1 \geq x^2, $$ that is, for all $x \geq \frac{1 + \sqrt{5}}{2}$.