Question

Show that (n log n + n²)³ is O(n⁶).

Short answer

$(\mathrm{nlogn}+{\mathrm{n}}^2{)}^3$is$O\left(n^6\right)$

Step-by-step solution

Step 1:

Big-O Notation $f\left(x\right)O\left(g\right(x\left)\right)$if there exitsts constants C and K such that

$\left|f\right(x\left)\right|\le C\left|g\right(x\left)\right|$

Whenever $x>k$

To proof

$(nlogn+n^2{)}^{3}O(n^6)$

$$\begin{gathered} n>0\log n\le n \\ n>1\log n>0 \end{gathered}$$

Choose $k=1$.For $n>1$

$$\begin{gathered} \left|\right(nlogn+n^2{)}^3|=nlogn+n^2{)}^3 \\ \le (n\left(n\right)+n^2{)}^3 \\ =(n^2+n^2{)}^3 \\ =(2n^2{)}^3 \\ =8n^6 \\ 8\left|n^6\right| \end{gathered}$$

C then needs to be chosen as at least 8, thus let us choose$C=8$

By the definition of the big O notation we then obtain that$(nlogn+n^2{)}^3$is$O\left(n^6\right)$ with $k=1$ and$C=8$