# 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 $\displaystyle x^4+5x$, which is approximately $\displaystyle x^4$. The denominator is also approximately $\displaystyle x^4$, so the whole function is O(1).

More formally, you can write a series of upper bounds, e.g.: $\displaystyle (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 $\displaystyle f(x) \leq C*g(x)$?

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

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