# Thread: big-o, but long division first

1. ## big-o, but long division first

How is long division done on something like this. The log is what I don't understand:

This problem is actually for a discrete math course. The problem says we must find the least n such that f(x) is O(x^n), but for now I'd just like to understand the long division.

Though, an answer and explanation for n, and witnesses C and k would be cool too.

2. One does not need long division here. In any case, I have not seen long division applied to non-polynomials, though there may be a way to extend it.

In rate of growth problems, log(x) is a little brother of x. Also, the rate of a polynomial is determined by its degree. Informally, the nominator here is dominated by $x^4+5x$, which is approximately $x^4$. The denominator is also approximately $x^4$, so the whole function is O(1).

More formally, you can write a series of upper bounds, e.g.: $(x^4+5\log x)/(x^4+1)\le(x^4+5\log x)/x^4\le(x^4+5x)/x^4\le\dots$. Some of those inequalities may not hold for all x, but only for x > k for some k.

3. How can you determine a constant C such that $f(x) \leq C*g(x)$?

would I continue with the bounds until I reached $\frac {x^4 + x^4}{x^4}$ which would yield 2?

4. Yes, this will work. Note that $5x\le x^4$ is false for x = 1 but is true for $x\ge 2$.