Prove the following big O: $n^2+n\log n \in O(n^{3/2})$

Question

Prove the following big O: $n^2+n\log n \in O(n^{3/2})$

I wanted to verify my proof:

$n^2+n\log n \leq n^2 + n^2 \text{ (for all $n$)}=2n^2$

Then we want $2n^2 \leq c\cdot n^{3/2}$ which means $2/\sqrt{n}\leq c$

My question is, can I choose my value of $n_0$, such that for all $n > n_0$, $n^2+n\log n \leq c\cdot n^{3/2}$, or should it be clear (somewhere hidden in the proof)

I'm wondering here if I can just choose $n_0 = 4$, and then say that $c$ must therefore by greater then $2/\sqrt{4}=4$. $c$ must be greater then $4$.

Is this correct?

Answer 1

Your proposition is incorrect.

$n^2$ is not in $O(n^{3\over2})$. Your crucial mistake is in going from $2n^2 \le cn^{3\over2}$ for big enough $n$ (which is the correct relation to prove) to the next step. Dividing by $n^{3\over2}$ leads to the equivalent $2\sqrt{n} \le c$, which is clearly not correct for any constant $c$ for big enough $n$.