edited by
16,142 views
39 votes
39 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?

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

5 Answers

Best answer
48 votes
48 votes

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

edited by
30 votes
30 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. 

23 votes
23 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.
9 votes
9 votes

Answer is D.

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

Answer:

Related questions

24 votes
24 votes
6 answers
3
go_editor asked Apr 23, 2016
5,187 views
Let $x_n$ denote the number of binary strings of length $n$ that contain no consecutive $0$s.The value of $x_5$ is $5$$7$$8$$16$