edited by
22,584 views
79 votes
79 votes

Consider the following functions

  • $f(n) = 3n^{\sqrt{n}}$
  • $g(n) = 2^{\sqrt{n}{\log_{2}n}}$
  • $h(n) = n!$

Which of the following is true?

  1. $h(n)$ is $O(f(n))$
  2. $h(n)$ is $O(g(n))$
  3. $g(n)$ is not $O(f(n))$
  4. $f(n)$ is $O(g(n))$
edited by

10 Answers

Best answer
72 votes
72 votes

$$\begin{array}{|l|l|l|}\hline \text{} &  \textbf{n= 256} & \textbf{n = 65536} \\ \hline \text{$f(n) = 3n^{\sqrt{n}}$} &  \text{$3 \times 256^{16}$} & \text{$3 \times 65536^{256}$}\\ & \text{$=3 \times {2^{128}}$} & \text{$ = 3 \times 2^{16 \times 256}$} \\ & & \text{$ = 3 \times 2^{4096}$}\\\hline \text{$g(n) = 2^{\sqrt{n}{\log_{2}n}}$} &  \text{$2^{16 \times 8}$}  & \text{$2^{256 \times 16}$} \\ & \text{$=2^{128}$} & \text{$ = 2^{4096}$}\\ \hline \text{$h(n) = n!$} & \text{$256!$} & \text{$65536!$}\\ & \text{$= O\left(\left(2^8\right)^{256}\right)$} & \text{$= O\left(\left(2^{16}\right)^{65536}\right)$} \\ & \text{$=O\left(2^{2048}\right)$} & \text{$=O\left(2^{1M}\right)$} \\ \hline\end{array}$$

Case of $h(n)$ is given only by an upper bound but factorial has higher growth rate than exponential. 

http://math.stackexchange.com/questions/351815/do-factorials-really-grow-faster-than-exponential-functions

$f(n)$ and $g(n)$ are having same order of growth as $f(n)$ is simply $3\times g(n)$ (we can prove this by taking $\log$ also). So, (d) is correct and all other choices are false. 

edited by
93 votes
93 votes

1. $f(n) = 3n^{\sqrt{n}}$
2. $g(n) = 2^{\sqrt{n}{\log_{2}n}} = (2^{\log_{2}n})^\sqrt{n} = (n^{\log_{2}2})^\sqrt{n} = n^{\sqrt{n}} $
3. $h(n) = n! = o(n^n)$

So, $f(n) = g(n) < h(n) $

Therefore, (D) is the correct option!

10 votes
10 votes

Ans - D)

h = n! , can also be written as 

h = nn (a weak upper bound on the factorial function n! <= nn , as each of the n terms in the factorial product is at most n ).

This eliminates options A AND B.

And by using log property on g(n) , we observe that f(n) and g(n) vary by just a constant term of 3. 

Thus this gives us the answer D.

5 votes
5 votes
f (n) and g (n) are asymptotically equal.

and f (n)=O (g (n)) iff g (n) is asymptotically greater or equal to f (n)  

so option D is correct :-)
Answer:

Related questions