Question

Arrange the functions \(\sqrt n ,{\rm{ }}1000\log n,{\rm{ }}n\log n,{\rm{ }}2n!,{\rm{ }}{2^n},{\rm{ }}{3^n},{\rm{ and }}\frac{{{n^2}}}{{1,000,000}}\) in a list so that each function is big-\(O\) of the next function.

Short answer

Functions arranged in a list so that each function is big-\(O\) of the next function can be given as below:

\(1000\log n,{\rm{ }}\sqrt n ,{\rm{ }}n\log n,{\rm{ }}\frac{{{n^2}}}{{1,000,000}}{\rm{, }}{2^n},{\rm{ }}{3^n},{\rm{ }}2n!{\rm{ }}\)

Step-by-step solution

Step 1:

We need to arrange given functions \(\sqrt n ,{\rm{ }}1000\log n,{\rm{ }}n\log n,{\rm{ }}2n!,{\rm{ }}{2^n},{\rm{ }}{3^n},{\rm{ and }}\frac{{{n^2}}}{{1,000,000}}\) in ascending order of their values. We can imply that ratio of two successive function also has to be in increasing order.

Step 2:

Also, we know that \(\log \) of any number is less than that number So, general mathematic rule states that,

\({\rm{logarithmic functions < power functions < exponential functions < factorials}}{\rm{.}}\)

Step 3:

So, the given functions in ascending order can be given as below

\(1000\log n,{\rm{ }}\sqrt n ,{\rm{ }}n\log n,{\rm{ }}\frac{{{n^2}}}{{1,000,000}}{\rm{, }}{2^n},{\rm{ }}{3^n},{\rm{ }}2n!{\rm{ }}\).

Hence, functions arranged in a list so that each function is big-\(O\) of the next function can be given as below:

\(1000\log n,{\rm{ }}\sqrt n ,{\rm{ }}n\log n,{\rm{ }}\frac{{{n^2}}}{{1,000,000}}{\rm{, }}{2^n},{\rm{ }}{3^n},{\rm{ }}2n!{\rm{ }}\)