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

kybudmanqm

kybudmanqm

Answered question

2022-09-04

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 ( 2 x + 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)?

Answer & Explanation

Peyton Cox

Peyton Cox

Beginner2022-09-05Added 18 answers

Explanation:
x sin x O ( x ) , x log ( 2 x + 4 ) O ( x log x ) , x 3 + 1 x 2 + 1 O ( x ) .
Jazmin Bryan

Jazmin Bryan

Beginner2022-09-06Added 12 answers

Step 1
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 ) C x log ( x ) .
Step 2
If you take the C = 1, then you just have to be certain that sin ( x ) log ( x ). That will happen once log ( x ) 1 since sin ( x ) 1. Repeat the process for each part. You don't have to use the same C for each part.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?