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?

1. $f\left(n\right)=O\left(g\left(n\right)\right); g\left(n\right)=O\left(h\left(n\right)\right)$
2. $f\left(n\right) = \Omega\left(g\left(n\right)\right); g(n) = O\left(h\left(n\right)\right)$
3. $g\left(n\right) = O\left(f\left(n\right)\right); h\left(n\right)=O\left(f\left(n\right)\right)$
4. $h\left(n\right)=O\left(f\left(n\right)\right); g\left(n\right) = \Omega\left(f\left(n\right)\right)$

I understand growth rate h(n)<f(n)<g(n)

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

g(n)=Ω(f(n))???
How f(n) can be the lower bound of g(n)?

when n=1,then g(n)=1,f(n)=2.

Coreman says it has to give right answer for all values of n.

$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

take log both side and compare function

n! Factorial is always greater than exponential. And 2^n always > n^logn (Remember the sequence of what has higher growth rate than compared to others)

Hence h(n)<f(n)<g(n)

So h(n)= Of(n) and f(n)=Og(n)

We can also write f(n)=Og(n) as g(n)=omega(f(n))

Hence option D is correct.

Subscribe to GO Classes for GATE CSE 2022

$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.

$h(n)$ can be rewritten as : $\Large{2^{logn^{logn}}}$ $=2^{(logn)^2} \color{Red}< \ 2^n \ \{f(n)\}$

${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})$

I think in option A because of 2nd statement it is wrong. am i right?

This condition is violated by options A, B and C by first statements of each.

In option B and C this is correct. but for option A it is wrong.

f(n) = O(g(n))  implies  $2^{n}=O(n!)$    first statement is correct.

g(n)=O(h(n)) implies   $n!=O(n^{logn})$  second statement is false.

 $f(n)$ $g(n)$ $h(n)$ $n = 2^{10}$ $2^{1024}$ $1024!$ ${2^{10}}^{10} = 2^{100}$ $n = 2^{11}$ $2^{2048}$ $2048!$ $2^{121}$ Increase $2^{1024}$ $1025 \times 1026 \times \dots \times 2048$ $2^{21}$

So, growth rate is highest for $g(n)$ and lowest for $h(n)$. Option D.

by
Take log of all function with base 2

log(f(n)) = Log(2^n)  = n

log(g(n)) = Log(n!) = Log(n^n) // using sterling approximation = nlogn

Log(h(n)) = Log(n ^ logn) = log(n) * log(n).

It becomes clear now that h(n) < f(n) < g(n).

Looking at options D is only option which satisfy this constraints.

1 comment

In D, h(n) = O(f(n)), is this right?/

1 < loglogn < logn < n< n< nlogn < c< nn < cc^< n! .

1 comment

1 < loglogn < logn < n< n< nlogn < c< nn < cc^< n!

isn't n! = O(n^n)?

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

correct me if i'm wrong
2n
by