Question

Arrange the functions $\mathit{n}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{<}\mathit{n}\mathbf{(}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}{\mathbf{)}}^{\mathbf{3}\mathbf{/}\mathbf{2}}\mathbf{<}{\mathit{n}}^{\mathbf{4}\mathbf{/}\mathbf{3}}\mathbf{(}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}{\mathbf{)}}^{\mathbf{2}}\mathbf{<}{\mathit{n}}^{\mathbf{3}\mathbf{/}\mathbf{2}}\mathbf{<}{\mathit{n}}^{\mathbf{l}\mathbf{o}\mathbf{g}\mathbf{}\mathbf{n}}\mathbf{<}{\mathbf{2}}^{\mathbf{100}\mathbf{n}}\mathbf{<}{\mathbf{2}}^{{\mathbf{n}}^{\mathbf{2}}}\mathbf{<}{\mathbf{2}}^{\mathbf{2}\mathbf{n}}\mathbf{<}{\mathbf{2}}^{\mathbf{n}\mathbf{!}}$andin a list so that each function is big-O of the next function. [Hint: To determine the relative size of some of these functions, take logarithms]

Short answer

The order of the function is

$n\log n\log \log n<n(\log n{)}^{3/2}<n^{4/3}(\log n{)}^2<n^{3/2}<n^{\log n}<2^{100n}<2^{n^2}<2^{2n}<2^{n!}$

Step-by-step solution

Step 1: Order the function that are powers of n       

First let us consider the functions that are powers ofn

$n\log n\log \log n<n(\log n{)}^{3/2}<n^{4/3}(\log n{)}^2<n^{3/2}<n^{\log n}$

Here we know that$n^c$ if of higher order than$n^d$ when$c>d$

Therefore the order is$1<\frac{4}{3}<\frac{3}{2}<\log n$ whenn is large

$n\log n\log \log n<n(\log n{)}^{3/2}<n^{4/3}(\log n{)}^2<n^{3/2}<n^{\log n}$

Step 2: Order the function that are powers of 2

First let us consider the functions that are powers of 2

$2^{100n},2^{n^2},2^n!,2^{2}n$

Here we know that$2^c$ if of higher order than$2^d$ when$c>d$

Therefore the order is $100n<n^2<2^n<n!$

$2^{100n}<2^{n^2}<2^{2n}<2^{n!}$

Final Solution

Therefore arrange the function accordingly

$n\log n\log \log n<n(\log n{)}^{3/2}<n^{4/3}(\log n{)}^2<n^{3/2}<n^{\log n}<2^{100n}<2^{n^2}<2^{2n}<2^{n!}$