Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

"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.

share|improve this question
    
@Braindead, yes, I wasn't sure if I was on the right track at all. This is quickly becoming a major headache since I don't quite understand it. –  riista Jan 22 at 4:03

3 Answers 3

up vote 3 down vote accepted

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$.

share|improve this answer
    
You've really gone above and beyond. Thank you so much Braindead. –  riista Jan 22 at 5:16
1  
@riista My pleasure. Let me know if you need any clarifications. –  Braindead Jan 22 at 5:17

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}$.

share|improve this answer
    
I don't quite understand your methodology. What is going on in the numerator in your inequality? –  riista Jan 22 at 4:34
1  
The idea is that as $x$ approaches $\infty$, the $x^4$ term will dominate the other terms in the original numerator, so we try to bound it by something as simple as possible. When $x$ is "large enough", $x^4 \geq x$, so $x^4 + 2x - 7 \leq x^4 + 2x^4 - 7 = 3x^4 - 7$. (in this case large enough means $x \geq 1)$. From this we simply use the fact that for any real $x$, $3x^4 - 7 \leq 3x^4$. In terms you might be more familiar with, for this proof we have taken $x_0 = \frac{1 + \sqrt{5}}{2}$ and $c = 3$. –  Tim Jan 22 at 4:47
    
This is excellent. Thank you so much! –  riista Jan 22 at 5:06

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.

share|improve this answer
    
Is there a method without limits? What about $x_0$ (some people call it $k$ or $n_0$); how do I come to that figure? –  riista Jan 22 at 4:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.