I'd want to know how I can find the lowest integer n such that f(x) is big-O($x^n$) for
a) $f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$
I've fooled around with this a bit and tried going from
$\frac {x^4 + x^2 + 1}{x^3 + 1} \le \frac {x^4 + x^2 + x}{x^3 + 1} \le \frac {x^4 + x^2 + x}{x^3}$
but I'm honestly just taking wild stabs at the problem. The single fractional problem in my textbook talks about making the fraction larger by making the numerator bigger and/or the denominator smaller. That's the only basis I have for what is written above and I don't know how to progress from there.
b) $f(x) = \frac {x^4 + 5 \log x}{x^4 + 1}$
I've got no clue where to start with this one. I tried looking at it like as a combination of functions ($x^4 +5 \log x)$ but I have no idea what to do with 5 log x.
When writing your reply please try to keep it as simple as possible.
Edit (June 24):
Because the question asks the answer to use the lowest exponents possible, the book lists $2x$ where x > 1 as a possible solution for a) and $2x^0$ where x > 1 as a possible solution to b).
Best Answer
Intuitively, the idea is that the "order" of a function is that of its highest-order term. In $x^4 + x^2 + 1$, you can usually ignore everything except the $x^4$, and say that it is $O(x^4)$ and not $O(x^d)$ for any smaller $d < 4$. Similarly $x^3 + 1$ is of the order of $x^3$, and in general a polynomial of degree $d$ is of the order of $x^d$.
So in your first function $f(x) = f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$, the numerator is of order $x^4$ and the denominator is of order $x^3$, so the fraction $f(x)$ is of order $\frac{x^4}{x^3} = x$.
That's the idea of what's really going on, but to prove it formally, you can do the division: write $f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1} = x + \frac{x^2 - x + 1}{x^3 + 1}$, and observe that the remainder term $\frac{x^2 - x + 1}{x^3 + 1} = \frac{1}{x+1} \to 0$ as $x \to \infty$, so $f(x) = O(x)$ and not $O(x^{1 - \epsilon})$ for any $\epsilon > 0$.
You don't even have to do the division completely: just get rid of the $x^3$ terms from both numerator and denominator. Observe that $$f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1} = \frac{(x^4 + x^2 +1)/x^3}{(x^3 + 1)/x^3} = \frac{x + \frac{1}{x} + \frac{1}{x^3}}{1 + \frac{1}{x^3}}$$ and you can prove directly from this that $f(x) = O(x)$.
Similarly, for the second function, $f(x) = \frac {x^4 + 5 \log x}{x^4 + 1}$, both numerator and denominator are of the same order $x^4$, so you should expect the fraction to be $O(1)$. You can prove it by writing $$f(x) = \frac {x^4 + 5 \log x}{x^4 + 1} = \frac {(x^4 + 5 \log x)/x^4}{(x^4 + 1)/x^4} = \frac{1 + \frac{5 \log x}{x^4}}{1 + \frac{1}{x^4}} $$ and proving from there that $f(x) = O(1) = O(x^0)$.
(E.g. you can show that, for $c_1 = \frac12$ and $c_2 = 2$ (say) and sufficiently large $x$, we have $c_1 \le f(x) \le c_2$, since $f(x) \ge \frac{1}{1 +\frac1{x^4}} \ge \frac{1}{2}$ when $x \ge 1$, and similarly $f(x) \le \frac{1 + \frac{5\log x}{x^4}}{1} \le 2$ when $\frac{5 \log x}{x^4} \le 1$, which again is true for sufficiently "large" $x$. Actually in this case any constants $c_1 < 1 < c_2$ will do, since $\lim_{x\to\infty} \frac{f(x)}{x} = 1$, but we don't need all this just to prove that $f(x) = O(1)$.)