2
$\begingroup$

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.

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

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.