but how could g(n) is equal to best case of f(n)

g(n)=Ω(f(n))???

8,612 views

Consider the following functions:

- $f(n) = 2^n$
- $g(n) = n!$
- $h(n) = n^{\log n}$

Which of the following statements about the asymptotic behavior of $f(n)$, $g(n)$ and $h(n)$ is true?

- $f\left(n\right)=O\left(g\left(n\right)\right); g\left(n\right)=O\left(h\left(n\right)\right)$
- $f\left(n\right) = \Omega\left(g\left(n\right)\right); g(n) = O\left(h\left(n\right)\right)$
- $g\left(n\right) = O\left(f\left(n\right)\right); h\left(n\right)=O\left(f\left(n\right)\right)$
- $h\left(n\right)=O\left(f\left(n\right)\right); g\left(n\right) = \Omega\left(f\left(n\right)\right)$

$n! = O(n^{n})$

Now $2^{n}$ $n^{n}$ $n^{logn}$

take log $\Rightarrow$ n nlogn lognlogn

it's clear that among these 3 nlogn has the highest growth rate, Now compare n & lognlogn

n | lognlogn | |

n=8 | 8 | 9 |

n=16 | 16 | 16 |

n=32 | 32 | 25 |

So, after n = 16 , lognlogn is overtaking n, that's why lognlogn > n

So, $lognlogn<n<nlogn$ which implies only option D

Best answer

$g(n) = n!$.

On expanding the factorial we get $g(n) = O(n^n)$ :$$\begin{align*} n^n &> n^{\log n} \\ n^n &> 2^n \end{align*}$$This condition is violated by options $A$, $B$ and $C$ by first statements of each. Hence, they cannot be said to be TRUE.

Second statement of option $D$ says that $g(n)$ is asymptotically biggest of all.

Answer is option** (D).**

${2^{logn^{logn}}} = 2^{log (n^{log \space n})} = 2^{(log \space n)log \space n} $

$2^{(log n)log n} $ **NOT EQUAL** TO $2^{(log n)(log n)} \space or \space 2^{(log n)^2}$

example if $n=2^{1024}$ then $2^{(log n)log n} = 2^{(log {2^{1024}})log \space 2^{1024}} = 2^{1024*10} $

and $2^{(log n)(log n)} = 2^{(log 2^{1024})(log 2^{1024})} = 2^{(1024)*(1024)}$

also $h = n^{log \space n}= (2^{1024})^{log (2^{1024})} = (2^{1024})^{10} = (2^{1024})* (2^{1024})*(2^{1024}) ...$10 times so $(2^{1024})^{10} = (2^{1024*10}) $

Take log on both sides of the functions and compare each functions.

eg 2n n!

taking log on both sides

nlog(base 2) log(n!)

and put n = 2^128 or some 2^k values

ll get

nlog(base2) < log(n!)

and simlarly for 2^n and n^logn

now, 2^n > n^logn

so n! > 2^n > n^logn

Answer is (D).

correct me if i'm wrong

2n

Search GATE Overflow