GATE CSE 2008 | Question: 39

Question

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?

• A. $f\left(n\right)=O\left(g\left(n\right)\right); g\left(n\right)=O\left(h\left(n\right)\right)$
• B. $f\left(n\right) = \Omega\left(g\left(n\right)\right); g(n) = O\left(h\left(n\right)\right)$
• C. $g\left(n\right) = O\left(f\left(n\right)\right); h\left(n\right)=O\left(f\left(n\right)\right)$
• D. $h\left(n\right)=O\left(f\left(n\right)\right); g\left(n\right) = \Omega\left(f\left(n\right)\right)$

Comments

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

 

 

Answer 1

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