Question

List these functions so that each functions is big-O of the next function in the list: $\mathbf{(}\mathit{l}\mathit{o}\mathit{g}\mathit{n}{\mathbf{)}}^{\mathbf{3}}\mathbf{}\mathbf{}\mathbf{,}{\mathbf{n}}^{\mathbf{3}}\mathbf{/}\mathbf{1000000}\mathbf{}\mathbf{,}\sqrt{\mathbf{n}}\mathbf{}\mathbf{,}\mathbf{100}\mathit{n}\mathbf{+}\mathbf{101}\mathbf{}\mathbf{,}{\mathbf{3}}^{\mathbf{n}}\mathbf{}\mathbf{,}\mathit{n}\mathbf{!}\mathbf{}\mathbf{,}{\mathbf{2}}^{\mathbf{n}}\mathbf{}\mathbf{,}{\mathit{n}}^{\mathbf{2}}$.

Short answer

$(logn{)}^3<\sqrt{n}<100n+101<\frac{n^3}{1000000}<n^2{2}^n<3^n<n!$

Step-by-step solution

Big-O notation

Generally, the increasing order of function in Big-O notation is :

Constant functions

Logarithmic functions

Polynomial functions (in increasing order of degree)

Exponential function (in increasing order of the base)

Factorial functions

List the functions

The given function can be classified as:

$(logn{)}^3$is a logarithmic function

$\frac{n^3}{1000000}$is a polynomial function of degree 3

$\sqrt{n}$ is a polynomial function of degree $\frac{1}{2}$

$100n+101$is a polynomial function of degree 1

$3^n$is an exponential function with base 3

$n^3{2}^n$is a combination of an exponential and polynomial function (which has a lower order than the exponential functions with a higher base (that is, $3^n>n^2{2}^n$ when, $n\ge 13$), but a higher order than the polynomial functions).

$n!$ is a factorial function

Ordering the given functions in increasing order, we then obtain:

$(logn{)}^3<\sqrt{n}<100n+101<\frac{n^3}{1000000}<n^2{2}^n<3^n<n!$

Note: If the order in Big-O notation of $f\left(x\right)$is lower than $g\left(x\right)$, then this means that $f\left(x\right)$is $O\left(g\right(x\left)\right)$.