Question

Arrange the functions${\mathit{n}}^{\mathbf{n}}\mathbf{,}{\mathbf{(}\mathbf{log}\mathbf{}\mathit{n}\mathbf{)}}^{\mathbf{2}}\mathbf{,}{\mathit{n}}^{1.0001}\mathbf{,}{\mathbf{(}\mathbf{1}\mathbf{.}\mathbf{0001}\mathbf{)}}^{\mathbf{n}}\mathbf{,}{\mathbf{2}}^{\sqrt{log}}$₂nand$\mathbf{n}{\left(\log n\right)}^{\mathbf{1001}}$in 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

$(\log n{)}^2\in O\left(2^{\sqrt{{\log }_{2}n}}\right)\subset O\left(n(\log n{)}^{1001}\right)\in O\left(n^{1.0001}\right)\subset O(1.0001{)}^n\in O\left(n^n\right)$

Step-by-step solution

Compare the slowest-growing function

The slowest-growing function from the given function is$2^{\sqrt{{\log }_{2}n}}$

As,$\sqrt{{\log }_{2}n}<{\log }_{2}n$

$2^{\sqrt{{\log }_{2}n}}<2^{{\log }_{2}n}=n$ So the order is $O\left(n\right)$

Now compare the function with $(\log n{)}^2$since all the other given functions are$\Omega \left(n\right)$

First by taking log on the function$2^{\sqrt{{\log }_{2}n}}$ we get,

$\log \left(2^{\sqrt{{\log }_{2}n}}\right)+\sqrt{{\log }_{2}n}\log 2\in O\left(\sqrt{\log n}\right)$

Now for the other function${\left(\log n\right)}^2$ we get,

$\log \left((\log n{)}^2\right)=2\log \log n\in O(\log \log n)$

Let$x=\log n$

Now the two functions are$O\left(\sqrt{x}\right)$ and $O\left(\log x\right)$.

Here we know that $O(\log x)\subset O\left(\sqrt{x}\right)$,

Therefore$(\log n{)}^2\in O\left(2^{\sqrt{{\log }_{2}n}}\right)$

Compare the next closest to linear

The next functions are$n^{1.0001}$and$n(\log n{)}^{1001}$since the exponentials grow faster than polynomials,

First by taking log on the function$n^{1.0001}$we get,

$\log \left(n^{1.0001}\right)=1.0001\log n\in O(\log n)$

Now for the other function $n(\log n{)}^{1001}$we get,

$\log \left(n(\log n{)}^{1001}\right)=\log n+1001\log \log n$

Let$x=\log n$

Now the two functions are$1.0001x$ and $x+1001\log x$.

By finding the derivate of each w.r.tx we get,

1.0001 and$1+\frac{1001}{x}$

Therefore the function$n^{1.0001}$grows at an increasing rate of whereas the second function decreases with

Thus$n(logn{)}^{1001}\in O(n^{1.0001})$

Compare the other function

The functions$(1.0001{)}^n$and$n^n$ are the remaining functions

Here it is clear that$n>1.0001$

Therefore$(1.0001{)}^n\in O(n^n)$

Final Solution

Therefore arrange the function according to the comparison we made

$(\log n{)}^2\in O\left(2^{\sqrt{{\log }_{2}n}}\right)\subset O\left(n(\log n{)}^{1001}\right)\in O\left(n^{1.0001}\right)\subset O(1.0001{)}^n\in O\left(n^n\right)$