Joshua Foley

2022-07-03

Big O Notation - Prove .
My Attempt:
$C\left({n}^{4}\right)\ge \left(nlogn{\right)}^{2}-4$
i assumed $n>0$, so that $n>\mathrm{log}\left(n\right)$
$\left(n{\right)}^{2}>\left(\mathrm{log}n{\right)}^{2}$
${n}^{2}>{\mathrm{log}}^{2}\left(n\right)$
${n}^{4}>{n}^{2}\cdot {\mathrm{log}}^{2}\left(n\right)$

pampatsha

Expert

Explanation:
This is a sketch prove, it's not fully complete, but it should give you a hint:
Consider the function $f\left(x\right)=x-\mathrm{log}\left(x\right)\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}{f}^{\prime }\left(x\right)=\frac{x-1}{x}$, which is strictly positive for $x>1$, as such, f(x) this function is strictly increasing on $\left(1,+\mathrm{\infty }\right)\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}x>\mathrm{log}\left(x\right)\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}{x}^{2}>x\mathrm{log}\left(x\right)\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}{x}^{4}>{\left({x}^{2}\mathrm{log}\left(x\right)\right)}^{2}\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}\left({x}^{2}\mathrm{log}\left(x\right)\right)=O\left({x}^{4}\right)$

Do you have a similar question?