discrete math: Big-oh notation

Question

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 01:00 — TravisJ, Mar 24 '15 at 01:00
No, I edited it for clarification – Cintra Mar 24 '15 at 01:37 — Cintra, Mar 24 '15 at 01:37

score 2 · Accepted Answer · answered Mar 24 '15 at 01:03

Hint:

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.

score 0 · Answer 2 · answered Mar 24 '15 at 00:40

0

Hint:

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

answered Mar 24 '15 at 00:40

William Stagner

4,786

discrete math: Big-oh notation

2 Answers2