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

 

 

---

got it

---

h(n) = O(f(n)); g(n) = Ω(f(n))

• h(n) = O(f(n)): Does h grow no faster than f? Yes, because f > h. This part is TRUE.

• g(n) = Ω(f(n)): Does g grow at least as fast as f? Yes, because g > f. This part is TRUE.

Answer 1

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

Comments

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

---

@Shubhgupta yes

---

@ amarVashishth

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.

Answer 2

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

Comments

@Arjun Sir, I see that you have used this method to solve most of the complexity analysis Questions, but could you please tell me if I take log throughout and solve wont that work for all questions of this type?

Answer 3

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.

Comments

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

---

Yes. $h(n)=O(f(n))$ simply translates to, $h(n) \leq  f(n)$, which is true here.

---

logarithms are borderline magical man.

Answer 4

Answer is D.

1 < loglogn < logn < n^e < n^c < n^logn < cⁿ < nⁿ < c^{c^n} < n! .

Comments

1 < loglogn < logn < n^e < n^c < n^logn < cⁿ < nⁿ < c^{c^n} < n!

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

---

Very helpful

---

incorrect.   grows faster than n!. Ty by taking log. Please correct it.

Answer 5

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

Answer 6

g(n) > f(n) > h(n)
By looking at the options we can directly eliminate Options : A,B,C
Option D is correct answer