Show if $n \sqrt n \in O(n^4)$

Question

I'm quite confused as to how to solve this step by step. What I have done was graph this using Desmos graphing software to visually see it, and I can see that the $n \sqrt n $ is below $n^4$.

I thought I could do something like this:

$n \sqrt n \lt n^4$

$ \sqrt n \lt n^3$

$n^{1/2} \lt n^4$

$1 \lt n^4 / n^{1/2}$

$1 \lt n^{7/2}$

So based on this, $n \sqrt n$ is not bigO of $O(n^4)$. Is that correct? Or would I say it is BigO iff $n > 1$ ?

Thank you.

Answer 1

All boils down to $x\ge 1\implies x^2\ge x$ when multiplying both sides by $x$

For $n\ge 1$

• you have $\sqrt{n}\ge 1$ so $n\ge \sqrt{n}$
• you have also $n^3\ge n^2\ge n$ by the same principle

Gathering everything gives you $n^3\ge \sqrt{n}$, which formally has $n_0=1$ and $C=1$ from the big-O notation:

$\forall n\ge n_0$ then $\sqrt{n}\le Cn^3\iff \sqrt{n}=O(n^3)$

which is equivalent to $n\sqrt{n}=O(n^4)$ as you noticed yourself.

Answer 2

Why make things more complex than they are? Very simply, $\;n\sqrt n=o(n^4)$, so a fortiori, it is $O(n^4)$.

This being said, how do you proceed from $\sqrt n < n^3$ to $n^{1/2} < n^4$?

If you want to prove directly that $n\sqrt n=O(n^4)$ (or not), you have to prove the ratio $\,\frac{n\sqrt n}{n^4}$ is bounded by some constant $C$ for all $n$ large enough, and this constant is not necessarily $1$.

Answer 3

${{n\sqrt n}\over n^4}={1\over n^{5/2}}$ and $\lim_\limits{n\rightarrow +\infty}{1\over n^{5/2}}=0$.