Big $O$ notation proof: $f(n) = (n^5)(\log n)$ and I need to prove it is $O(n^7)$

Question

I'm having trouble wrapping my head around this. I have a function $f(n) = (n^5)(\log n)$ and I need to prove it is $O(n^7)$

I thought $n^5$ was the most significant term in this function so it should be $O(n^5)$, I don't know where $O(n^7)$ came from, it's not making sense to me.

Can anyone point me in the right direction?

Answer 1

First and foremost, $O$ is about giving an upper bound. Thus if you think it is $O(n^5)$ then it is also $O(n^7)$ and $O(n^6)$ and $O(n^{5.1})$ and $O(n^{2483624})$.

Second, it is not $O(n^5)$ as you cannot just ignore the logarithmic term there.

What you want to show is that there is a $C>0$ such that for all naturals $n$ (or for all sufficiently large $n$ it does not matter that much) you have $$n^5 \log n \le Cn^7.$$ This is true with $C=1$, as $\log n \le n$ for all $n \ge 1$ and thus $$ n^5 \log n \le n^5 n = n^6 \le n^7.$$

As you see the expression would also be $O(n^6)$, so the $n^7$ is indeed a bit arbitrarily chosen but its true. Just like $56$ is less than $60$ and also less than $70$.

Answer 2

You have $\ln n \le n$ for $n \in \mathbb N$. Therefore $$n^5 \ln n \le n^6 \le 1.n^7$$ which proves that $f(n) =O(n^7)$ at $\infty$

Answer 3

$\log n=o(n)$, hence $n^5\log n=n^5o(n)=o(n^6)$. A fortiori, it is $o(n^7)$, hence $O(n^7)$.