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

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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 votes

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

+19 votes

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

+15 votes

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

+12 votes

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.

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.

+8 votes

+2 votes

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,716 questions

46,750 answers

140,561 comments

58,405 users