# discrete math: Big-oh notation

I'm confused about how to solve big-oh notation problems using the definition and basic algebra. for example, a problem like this:

Prove that (x sin x + x log(2x + 4) + ((x^3 + 1)/(x^2 + 1)) is an element of big-oh(x log x).

hint:This will require both the algebraic properties of $O$ and its formal definition.

I'm thinking I can separate it into 3 parts and show each part is big-oh using limits(though I'm not sure that counts as an algebraic property) and the definition $(C,K)$?

I'd appreciate any help starting this out.

• Does the [] notation mean "integer part"? – TravisJ Mar 24 '15 at 1:00
• No, I edited it for clarification – Cintra Mar 24 '15 at 1:37

Yes you want to break them down. Think about how you might bound them (get rid of the messy stuff). For example, you want so say that $x\sin(x)=O(x\log(x))$. You need to say something to the effect that
$$x\sin(x) \leq Cx\log(x).$$
If you take the $C=1$, then you just have to be certain that $\sin(x)\leq \log(x)$. That will happen once $\log(x)\geq 1$ since $\sin(x)\leq 1$. Repeat the process for each part. You don't have to use the same $C$ for each part.
$$x\sin x \in O(x), \quad x\log(2x+4) \in O(x\log x), \quad \frac{x^3+1}{x^2+1}\in O(x).$$