Help understanding Big O notation

[Aaron Buckley]

First, I don't know if this is the right place so if not, please direct me. Thank you.

As for the question, I am in a discrete mathematics class online. The instructor is practically non-existent when asking for help simply saying to "refer to the book for clarification". I have scoured google, but every explanation I read seems to skip steps or miss chunks of explanations and leaves me lost. They seem to bring numbers out of no where. I understand I will probably get that here a bit as well, but with an open thread instead of a closed one I would imagine I would be able to ask for help in those specific area's as they arise.


The specific question is currently on my homework as follows:

Find the least integer n such that f (x) is O(xn) for each of these functions.

a) If f(x) = 2x² + x³logx then the least integer n is

Now, I have been looking for answers and these happen to be commonly used questions so I know the answer is 4. But I don't know how they got there because the next part leaves me just as clueless:

b) If

then the least integer n is

When looking at other explanations there are steps that read as follows:

(x³logx) = x⁴ = x⁵

And I just really feel like I am missing some set of rules or something and would appreciate help with being walked back through the first question so I can reflect my understanding with the second.

 

[fresh_42]

First, I don't know if this is the right place so if not, please direct me. Thank you.

As for the question, I am in a discrete mathematics class online. The instructor is practically non-existent when asking for help simply saying to "refer to the book for clarification". I have scoured google, but every explanation I read seems to skip steps or miss chunks of explanations and leaves me lost. They seem to bring numbers out of no where. I understand I will probably get that here a bit as well, but with an open thread instead of a closed one I would imagine I would be able to ask for help in those specific area's as they arise.


The specific question is currently on my homework as follows:

Find the least integer n such that f (x) is O(xn) for each of these functions.

a) If f(x) = 2x² + x³logx then the least integer n is

Now, I have been looking for answers and these happen to be commonly used questions so I know the answer is 4. But I don't know how they got there because the next part leaves me just as clueless:

b) If View attachment 231824 then the least integer n is

When looking at other explanations there are steps that read as follows:

(x³logx) = x⁴ = x⁵

And I just really feel like I am missing some set of rules or something and would appreciate help with being walked back through the first question so I can reflect my understanding with the second.

You should really have written $O(x^n)$.

Now the trick is to get an upper bound. How can you make $f(x)=2x^2+x^3\log x$ bigger, such that $f(x) \leq \ldots \leq C \cdot x^n = O(x^n)$ is true for some constant $c\,?$

 

[Aaron Buckley]

You should really have written $O(x^n)$.

Now the trick is to get an upper bound. How can you make $f(x)=2x^2+x^3\log x$ bigger, such that $f(x) \leq \ldots \leq C \cdot x^n = O(x^n)$ is true for some constant $c\,?$

I haven't seen anything mention upper bounds yet so I am not sure... Isn't the upper bound the highest exponent in terms of other mathematics? If that is the case the upper bound here would be 3 because x³?


For reference this is a link to the website that made the most sense to me, but I still felt like I was missing some key element(s):
http://www.slader.com/discussion/question/find-the-least-integer-n-such-that-f-x-is-oxn-for-each-of-these-functions/

 

[fresh_42]

I haven't seen anything mention upper bounds yet so I am not sure... Isn't the upper bound the highest exponent in terms of other mathematics? If that is the case the upper bound here would be 3 because x³?

$n=3$ isn't enough, because we still have the logarithm term.
So we get $f(x)=2x^2+x^3\log x < 3\cdot x^3 \log x <3\cdot x^3 \cdot x = 3x^4 =O(x^4)$.

Of course we cannot use any upper bound, we are looking for the minimal one in terms of $x^n$, so $\log x < x$ does the job. The constant $C$ however, can be chosen as big as we want to, as long as it is a constant. At least this is how the $O(.)$ notation is used. E.g. Wikipedia defines on https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition $f(x)=O(g(x)$ iff $|f(x)| \leq C \cdot g(x)$ for sufficiently large $x \geq x_0$.

 

[Aaron Buckley]

$n=3$ isn't enough, because we still have the logarithm term.
So we get $f(x)=2x^2+x^3\log x < 3\cdot x^3 \log x <3\cdot x^3 \cdot x = 3x^4 =O(x^4)$.

Of course we cannot use any upper bound, we are looking for the minimal one in terms of $x^n$, so $\log x < x$ does the job. The constant $C$ however, can be chosen as big as we want to, as long as it is a constant. At least this is how the $O(.)$ notation is used. E.g. Wikipedia defines on https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition $f(x)=O(g(x)$ iff $|f(x)| \leq C \cdot g(x)$ for sufficiently large $x \geq x_0$.

So do we just choose any number for C? Also, I still don't know how C and k are used to solve these. What do they represent? Because my answers so far are looking for the exponent n.

Secondly, is n just going to be the highest exponent in the problem once log's are solved? Also where did the 3 come from in:

3⋅x3logx

 

[fresh_42]

So do we just choose any number for C?

One which is needed. It doesn't matter which as the $O(.)$ notation is only a statement about a general behavior. $x^2$ grows slower than $x^3$ and $x^3\log x$ grows slower than $x^4$, so all in all we get a growth which is less than $3x^4$. The $x-$term dominates the growth for large $x$ such that the constant $C$, in our case $C=3$ simply doesn't play a role anymore.

Also, I still don't know how C and k are used to solve these. What do they represent?

The tendency of growth of $f(x)$. It is requested to chose a polynomial in $x$ as upper bound. Usually one would be a bit more strict and write $f(x)=2x^2+x^3\log x = O(x^3\log x)$ which is a bit more accurate. But here we also have to find an upper bound for $\log x$ as a polynomial of $x$.

Because my answers so far are looking for the exponent n.

It's all about behavior. $f(x) \sim x^3\log x < x^4$.

Secondly, is n just going to be the highest exponent in the problem once log's are solved? Also where did the 3 come from in:

We can always have $f(x)=2x^2+x^3\log x < x^{100}$ but this would be far to rough as an estimation. Better is, see above $O(x^3\log x)$ but as requested by the exercise, it should be a polynomial in $x$, so $x^3\log x < x^4$ is our next best choice. We have to stay above the value of $f(x)$, but as close as possible.

The major uses of this notation are in a) complexity theory and in b) physics.

• Imagine an algorithm for some problem. Let's say, the problem has an input of length $n$ and the algorithm stops after $f(n)$ arithmetic operations. Now imagine further, that we have done a precise count of the number of required arithmetic operations in a worst case scenario and found $f(n)=3n+n\log^3n+5n\log n \log \log n$. Now in order to compare the runtime of our algorithm to others, it is convenient to say how many operations it needs. So instead of this bulky formula, we would say instead: it runs in $O(n^4)$ many operations, which is said in polynomial time. This is better than algorithms which need exponential time, say $O(2^n)$, but worse than $O(n^3)$. Now in that case, the comparison with another algorithm which runs in $O(n^3)$, we would give a better estimation and state that our algorithm needs $f(n)=O(n\log^3 n)$ operations which is less than the other one with $O(n^3)$.
  
  
• In physics, there are many functions which are approximated by linear ones. E.g. $e^x=\sum_{n=0}^{\infty}\dfrac{x^n}{n!}$. For small values of $x$, i.e. those close to zero, we have $e^x=1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6}+\ldots = 1+x +\text{rest}$ and the rest is small for those $x \sim 0$. To be a bit more precise than just writing "rest", one writes $e^x=1+x+O(x^2)$ for small $x$, as all higher powers are swallowed by the $x^2-$term, i.e. they do contribute less than $C\cdot x^2$ does. It indicates that the linear term $1+x$ is taken as approximation plus an error in the magnitude of $C\cdot x^2=O(x^2)$. For $x>1$ the entire thing is far from being a good approximation, as then the terms of higher powers get more and more relevant and the function explodes beyond this value.

 

[SSequence]

There is a small point that may be worth highlighting ... when one says something along the lines of:
"Find the smallest $n \in \mathbb{N}$ such that, for a given function $f$, we have $f \in O(x^n)$"

There would generally be two parts to showing it (at least whenever $n \ge 1$):
(1) We must show that $f \notin O(x^{n-1})$
(2) We must show that $f \in O(x^n)$

On the other hand, suppose we just have something like:
"Find some $n \in \mathbb{N}$ such that, for a given function $f$, we have $f \in O(x^n)$"

In that case we just have to find some (non-unique) value $n$ such that $f \in O(x^n)$. And of course any value greater than that given value will also work because of the fact that $O(x^n) \subseteq O(x^{n+1})$.

 

[fresh_42]

And of course any value greater than that given value will also work because of the fact that $O(x^n) \subseteq O(x^{n+1})$.

... for $|x|>1$. For $|x|<1$ it is the other way around: $O(x^{n+1}) \subset O(x^n)$. Just for completion, as we often have the Taylor series at $x=0$ here and people write $+O(x^2)$.

 

[Aaron Buckley]

The major uses of this notation are in a) complexity theory and in b) physics.

• Imagine an algorithm for some problem. Let's say, the problem has an input of length nnn and the algorithm stops after f(n)f(n)f(n) arithmetic operations. Now imagine further, that we have done a precise count of the number of required arithmetic operations in a worst case scenario and found f(n)=3n+nlog3n+5nlognloglognf(n)=3n+nlog3⁡n+5nlog⁡nlog⁡log⁡nf(n)=3n+n\log^3n+5n\log n \log \log n. Now in order to compare the runtime of our algorithm to others, it is convenient to say how many operations it needs. So instead of this bulky formula, we would say instead: it runs in O(n4)O(n4)O(n^4) many operations, which is said in polynomial time. This is better than algorithms which need exponential time, say O(2n)O(2n)O(2^n), but worse than O(n3)O(n3)O(n^3). Now in that case, the comparison with another algorithm which runs in O(n3)O(n3)O(n^3), we would give a better estimation and state that our algorithm needs f(n)=O(nlog3n)f(n)=O(nlog3⁡n)f(n)=O(n\log^3 n) operations which is less than the other one with O(n3)O(n3)O(n^3).
  
  
• In physics, there are many functions which are approximated by linear ones. E.g. ex=∑∞n=0xnn!ex=∑n=0∞xnn!e^x=\sum_{n=0}^{\infty}\dfrac{x^n}{n!}. For small values of xxx, i.e. those close to zero, we have ex=1+x+x22+x36+…=1+x+restex=1+x+x22+x36+…=1+x+reste^x=1+x+\dfrac{x^2}{2}+\dfrac{x^3}{6}+\ldots = 1+x +\text{rest} and the rest is small for those x∼0x∼0x \sim 0. To be a bit more precise than just writing "rest", one writes ex=1+x+O(x2)ex=1+x+O(x2)e^x=1+x+O(x^2) for small xxx, as all higher powers are swallowed by the x2−x2−x^2-term, i.e. they do contribute less than C⋅x2C⋅x2C\cdot x^2 does. It indicates that the linear term 1+x1+x1+x is taken as approximation plus an error in the magnitude of C⋅x2=O(x2)C⋅x2=O(x2)C\cdot x^2=O(x^2). For x>1x>1x>1 the entire thing is far from being a good approximation, as then the terms of higher powers get more and more relevant and the function explodes beyond this value.

I am currently studying computer sciences and want to do software development, so I am thinking I will probably be more in the first scenario because it mentions algorithms.

One which is needed. It doesn't matter which as the O(.)O(.)O(.) notation is only a statement about a general behavior. x2x2x^2 grows slower than x3x3x^3 and x3logxx3log⁡xx^3\log x grows slower than x4x4x^4, so all in all we get a growth which is less than 3x43x43x^4. The x−x−x-term dominates the growth for large xxx such that the constant CCC, in our case C=3C=3C=3 simply doesn't play a role anymore.

So was C only 3 because that's what I thought the upper boundary would be?

We can always have f(x)=2x2+x3logx<x100f(x)=2x2+x3log⁡x<x100f(x)=2x^2+x^3\log x < x^{100} but this would be far to rough as an estimation. Better is, see above O(x3logx)O(x3log⁡x)O(x^3\log x) but as requested by the exercise, it should be a polynomial in xxx, so x3logx<x4x3log⁡x<x4x^3\log x < x^4 is our next best choice. We have to stay above the value of f(x)f(x)f(x), but as close as possible.

I understand that 100 would be too large because its looking for the smallest snumber. But x³logx = x⁴ and the answer is 4. Is this just coincidence or is the answer going to consistently be the highest found power?

 

[SSequence]

... for $|x|>1$. For $|x|<1$ it is the other way around:

Sorry I am a little confused about this. We are (presumably) talking about functions (either from $\mathbb{N}$ to $\mathbb{N}$ OR from $\mathbb{R}$ to $\mathbb{R}$) such that $x \mapsto x^n$ or $x \mapsto x^{n+1}$ etc. We are assuming $n$ to be the constant and $x$ to be the variable.

I am having difficulty seeing how $O(x^n) \subseteq O(x^{n+1})$ could fail (both for $\mathbb{N}$ or $\mathbb{R}$ as domain/codomain) any given $n \in \mathbb{N}$.

 

[Aaron Buckley]

... for $|x|>1$. For $|x|<1$ it is the other way around: $O(x^{n+1}) \subset O(x^n)$. Just for completion, as we often have the Taylor series at $x=0$ here and people write $+O(x^2)$.

There is a small point that may be worth highlighting ... when one says something along the lines of:
"Find the smallest $n \in \mathbb{N}$ such that, for a given function $f$, we have $f \in O(x^n)$"

There would generally be two parts to showing it (at least whenever $n \ge 1$):
(1) We must show that $f \notin O(x^{n-1})$
(2) We must show that $f \in O(x^n)$

On the other hand, suppose we just have something like:
"Find some $n \in \mathbb{N}$ such that, for a given function $f$, we have $f \in O(x^n)$"

In that case we just have to find some (non-unique) value $n$ such that $f \in O(x^n)$. And of course any value greater than that given value will also work because of the fact that $O(x^n) \subseteq O(x^{n+1})$.

And now these have me lost. So i understand that ∈ is element. So ƒ∈O(xⁿ) means the function is an element of O right? So it is asking which number is the smallest value of n that allows that function to be a element of that group?

To do this you say we need to prove that 1 minus the number cannot be a member of the group and that the number can be a member of that group correct?

Then, in a different problem, we could have it ask to choose any number that makes it an element? And this would imply that any number larger than that would also be an element? Why, however I am confused on. What is ⊆?

 

[fresh_42]

I am currently studying computer sciences and want to do software development, so I am thinking I will probably be more in the first scenario because it mentions algorithms.

In this case you should reread this section, as it likely is confusing, because I packed it in a few lines.

So was C only 3 because that's what I thought the upper boundary would be?

$3$ was to cover the two terms and be on the secure side. Constants are ignored in the $O(.)$ notation, so it doesn't matter. However, this is only half of the truth. It is right, that the $O(.)$ notation doesn't bother any constants. On the other hand, there are algorithms, for which the constant is so high, that it does bother for real cases. An algorithm which is linear in the input length, but requires $10^{100}$ steps isn't practicable although it's linear in time. So sometimes, the constant is important and the $O(.)$ doesn't reflect the real situation. But generally, it is a convenient measure to distinguish the runtimes or space of algorithms.

I understand that 100 would be too large because its looking for the smallest number. But x³logx = x⁴ and the answer is 4. Is this just coincidence or is the answer going to consistently be the highest found power?

No, we count the powers: three for $x$ and one for $\log x$, adds up to $4$. The estimation is $\log x < x \Longrightarrow x^3\log x < x^3\cdot x=x^4$

 

[fresh_42]

Sorry I am a little confused about this. We are (presumably) talking about functions (either from $\mathbb{N}$ to $\mathbb{N}$ OR from $\mathbb{R}$ to $\mathbb{R}$) such that $x \mapsto x^n$ or $x \mapsto x^{n+1}$ etc. We are assuming $n$ to be the constant and $x$ to be the variable.

I am having difficulty seeing how $O(x^n) \subseteq O(x^{n+1})$ could fail (both for $\mathbb{N}$ or $\mathbb{R}$ as domain/codomain) any given $n \in \mathbb{N}$.

No, I'm confused. I should stop writing this late. I just wanted to emphasize that an estimation $e^x=1+x+O(x^2)$ fails for $|x|>1$ whereas it is correct for $|x|<1$. I probably phrased it poorly.

 

[Aaron Buckley]

3 was to cover the two terms and be on the secure side. Constants are ignored in the O(.) notation, so it doesn't matter. However, this is only half of the truth. It is right, that the O(.) notation doesn't bother any constants. On the other hand, there are algorithms, for which the constant is so high, that it does bother for real cases. An algorithm which is linear in the input length, but requires 10^{100} steps isn't practicable although it's linear in time. So sometimes, the constant is important and the O(.) doesn't reflect the real situation. But generally, it is a convenient measure to distinguish the runtimes or space of algorithms.

So, we can solve these specific questions without using C and k? Also, which two terms did 3 cover and in what way did it cover them?

No, we count the powers: three for x and one for log x, adds up to 4. The estimation is logx<x⟹x3logx<x3⋅x=x4

So we chose x³log x instead of 2x² because it had the highest visible exponent correct? So if the 2x² would have been 2x⁵ we would have gone with that instead of the log correct? Which would change the answer to 5. However if the log was changed to x⁵log x then it would be 5 for the exponent plus 1 for the log x making the answer 6?

 

[fresh_42]

So, we can solve these specific questions without using C and k?

Not sure what you mean by $C$ and $k$. I only talked about the first example, where there is neither nor. The $O(g(x))$ notation has a hidden constant: $O(g(x))=C\cdot g(x)$ for some constant (= independent of $x$) $C$.

Also, which two terms did 3 cover and in what way did it cover them?

$f(x)=2x^2+1\cdot x^3+\log x < 3 x^3\log x$ without thinking about the special value of $C=3$. I could as well have written $f(x)< 10x^3\log x$. I just took the coefficients $2$ and $1$ and wrote $3$ as its sum.

So we chose x³log x instead of 2x² because it had the highest visible exponent correct? So if the 2x² would have been 2x⁵ we would have gone with that instead of the log correct?

Yes.

Which would change the answer to 5. However if the log was changed to x⁵log x then it would be 5 for the exponent plus 1 for the log x making the answer 6?

Yes.

But again, usually people write the $\log$ expressions separately, i.e. use polynomials in $x,\log x,\log\log x$ and sometimes even $\log \log \log x$. But here we are requested to only use polynomials in $x$.

 

[SSequence]

And now these have me lost. So i understand that ∈ is element. So ƒ∈O(xⁿ) means the function is an element of O right? So it is asking which number is the smallest value of n that allows that function to be a element of that group?

Generally speaking, you can't say that some function is an element of $O$. What you can say is that some function is an element of $O(g)$ (where $g$ is some function). You can think of $O(g)$ as representing a "collection" of functions.

So when we write something like $f \in O(x^n)$ we are just really saying that the function $f$ belongs to the collection $O(x^n)$. Of course $x^n$ here is *actually* the short-hand for the function $x \mapsto x^n$.

To do this you say we need to prove that 1 minus the number cannot be a member of the group and that the number can be a member of that group correct?

Yes, pretty much.

Then, in a different problem, we could have it ask to choose any number that makes it an element? And this would imply that any number larger than that would also be an element?

More or less, yes that's what I was saying.

Why, however I am confused on. What is ⊆?

$A \subseteq B$ means $A$ is a subset of $B$. For example, as you may have seen/read that this is true when a given set $B$ contains all elements of some set $A$. In our case, informally, the "sets" are sets that contain functions (as elements).

So we just say $O(x^2) \subseteq O(x^3)$ to mean that every function that is in $O(x^2)$ is also in $O(x^3)$.

 

[fresh_42]

Here is an actual example: https://en.wikipedia.org/wiki/Strassen_algorithm

Ordinary matrix multiplication needs $n^3$ multiplications and additions of numbers. However it can be done in $n^{\log_2 7}$ multiplications to the expense of additional additions. This estimation is exact for lengths of powers of two, i.e. $n=2^k$. For the numbers in between we get additional operations which are put in the constant of the $O(n^{2.807})$ notation.

 

[Aaron Buckley]

Not sure what you mean by C and k. I only talked about the first example, where there is neither nor. The O(g(x)) notation has a hidden constant: O(g(x))=C⋅g(x) for some constant (= independent of x) C.

I have just seen other sources immediately jump to solving C and k when I look up guides on solving these problems so I have been under the impression this entire time that those were important parts of solving for n.

(x)=2x2+1⋅x3+logx<3x3logx without thinking about the special value of C=3 I could as well have written f(x)<10x3logx. I just took the coefficients 2 and 1 and wrote 3 as its sum.

So is there any significance to doing this step? Or does adding the coefficients make no difference as long as the chosen coefficient is larger than their sum?

But again, usually people write the log expressions separately, i.e. use polynomials in x,logx,loglogx, and sometimes even logloglogx. But here we are requested to only use polynomials in x.

So, in case I am asked differently in future questions, what would these notations look like?

 

[fresh_42]

So is there any significance to doing this step? Or does adding the coefficients make no difference as long as the chosen coefficient is larger than their sum?

Yes. It makes no difference and before I try to find out for which $x$ on the $2x^2$ term is swallowed by what we have available between $x^3\log x$ and $x^4$, i.e. for which $x$ it is true that $2x^2+x^3\log x < x^4$ it's as good to say $2x^2+x^3\log x < 3\cdot x^4$ and not having to count peas.

So, in case I am asked differently in future questions, what would these notations look like?

In our case of $f(x)=2x^2+x^3 \log x$ it would be $f(x)=O(x^3\log x)$ since the $x^3-$term dominates the square term. It is more precise than $O(x^4)$. See my little explanation of algorithms in post #6. A multivariate polynomial looks like $p(X_1,X_2,\ldots) = \sum_{(i_1,i_2,\ldots ,i_n)} c_{(i_1,i_2,\ldots ,i_n)}X_{i_1}^{p_1}\cdot \ldots \cdot X_{i_n}^{p_n}$. Now just set $X_1=x, X_2=\log x, X_3=\log x \log x$ etc.

 

[Aaron Buckley]

Ok. So this is definitely helping me understand this better. I went ahead and answered the next few problems as follows:

b) If

then the least integer n is 5

Because 3x⁵ is greater than (log x)⁴

c) If

then the least integer n = 0

Because dividing the two terms gives you 1+ ((x²)/(x⁴+1)) and since the quotient has no exponent for x, n=0

I got those two right. But the next confuses me.

d) If

then the least integer n =

This can be simplified by removing the log. Since we can assume log x ≤ x, we can replace 5log x with 5x correct? this at least puts the terms in the same form, but I am not sure what to do next because division doesn't seem to do anything.

 

[fresh_42]

I assume that $d)$ reads $f(x)=\dfrac{x^3+5\log x}{x^4+1}$. So we have $f(x)< \dfrac{2x^3}{x^4}=2\dfrac{1}{x}$. Now for what $n$ is $2\dfrac{1}{x} < 2\cdot x^n\,?$

 

[Aaron Buckley]

I assume that $d)$ reads $f(x)=\dfrac{x^3+5\log x}{x^4+1}$. So we have $f(x)< \dfrac{2x^3}{x^4}=2\dfrac{1}{x}$. Now for what $n$ is $2\dfrac{1}{x} < 2\cdot x^n\,?$

So, To get to 2x³, do we first ignore 5log x because x³ has a higher exponent? Then x³ < 2x³?

Further do we ignore the +1 in the denominator because x⁴ is a higher power? But since we already have an inequality by altering the numerator we do not need to create the coefficient of 2 for the denominator?

Next we have the division gives us a quotient of 2 with a remainder of 1/x? To solve this since we have x in the denominator we need to raise it to a negative power correct? In this case it would be -1?

 

[SSequence]

Ok. So this is definitely helping me understand this better. I went ahead and answered the next few problems as follows:

b) If f(x)=3x⁵+(log x)⁴ then the least integer n is 5

Because 3x⁵ is greater than (log x)⁴

If one is being formal, this doesn't quite do it. As I mentioned in post#7 you would have to show two separate points:
(1) $f \notin O(x^4)$
(2) $f \in O(x^5)$

Given your reasoning, it is clear that you are reasoning about (2). However, when you are considering the least natural number (or perhaps integer?) $n$, you have to consider (1) too.

Here is how you can show both more formally I suppose:
(2) $f \in O(x^5)$

$f(x)=3x^5+(log(x))^4$ for all $x$

Using $log(x)<x$, we have for all $x>0$:
$3x^5+(log(x))^4 \le 3x^5+(x)^4$

for all $x\ge 1$
$3x^5+(x)^4 \le 3x^5+(x)^4.x=3x^5+(x)^5=4x^5$

If you follow these inequalities more carefully, what we have just shown is that:
for all $x\ge 1$
$f(x) \leq 4x^5$
And, by definition, that shows that $f \in O(x^5)$.

=========================================

At any rate, regardless of whether there was much need to go into that much detail (which depends on level of formality) regarding (2), one would still need to mention (1).

Here is how one can consider it more formally in this case:
(1) $f \notin O(x^4)$

$f(x)=3x^5+(log(x))^4$ for all $x$
$3x^5+(log(x))^4>3x^5$ for all $x$


$3x^5>3x^4$ for all $x>1$
$3x^5>9x^4$ for all $x>3$
$3x^5>27x^4$ for all $x>4$
...
More generally, for any arbitrary function $Cx^4$ where $C$ is of form $3^c$ (where $c \in \mathbb{N}^+$) we have:
$3x^5>Cx^4=3^c x^4$ for all $x>3^{c-1}$
Some reflection would show that this is enough to prove $f \notin O(x^4)$.

======================================

Of course you can write this differently (I just wrote it the way I felt it easier). But, generally speaking, one should ideally be aware that (1) must be considered in addition to (2).

Edit: Generally, I think for (1), one can say something generic like:
for all $x$
$f(x)=3x^5+(log(x))^4>3x^5$
Then one can say that because $3x^5 \notin O(x^4)$ and $f(x) \ge 3x^5$ (for all $x$), it follows that $f \notin O(x^4)$.

 

[fresh_42]

So, To get to 2x³, do we first ignore 5log x because x³ has a higher exponent? Then x³ < 2x³?

Since $x^3+5\log x \nleq x^3$ we have to go to $x^3+5\log x \leq 2x^3$. We do not ignore terms, we transform them into terms of higher order to the expense of the constant.

Further do we ignore the +1 in the denominator because x⁴ is a higher power?

No, we are looking for an upper bound and $\dfrac{1}{x^4+1}<\dfrac{1}{x^4}$ which is why we can drop $+1$.

But since we already have an inequality by altering the numerator we do not need to create the coefficient of 2 for the denominator?

No, as said, we simplify the expression by changing it to a slightly higher bound such that the general behavior isn't affected. And the behavior of the function is driven be the $x-$terms and not the constants. As it was in the denominator here, we don't have to adjust the constant: dropping $+1$ did the job.

Next we have the division gives us a quotient of 2 with a remainder of 1/x? To solve this since we have x in the denominator we need to raise it to a negative power correct? In this case it would be -1?

Yes. $f(x)< \dfrac{2}{x} = C\cdot \dfrac{1}{x} = O(n^{-1})$. This is a bit unusual, as in case of algorithms we normally don't get fractions. I would have said $f(x)=O(1)$, which means constant, but you are right, if integers are allowed we will get $-1$.