The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
1.5k 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)$

asked in Algorithms by Veteran (59.4k points)
edited by | 1.5k views
0
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))???

5 Answers

+19 votes
Best answer

$g(n) = n!$ on expanding factorial we get $g(n) = \mathcal{O}(n^n)$ :
$$\begin{align*} n^n &> n^{\log n} \\ n^n &> 2^n \end{align*}$$
this condition is violated by option A, B and C by first statements of each Hence, they cannot be said true.

second statement of option D says that $g(n)$ is asymptotically biggest of all.

answer = option D

answered by Boss (30.6k points)
selected by
+1
$h(n)$ can be rewritten as : $\Large{2^{logn^{logn}}}$ $=2^{(logn)^2}  \color{Red}< \ 2^n \ \{f(n)\}$
+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. 

answered by Veteran (339k points)
+10 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.
answered by Boss (42.4k points)
+7 votes

Answer is D.

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

answered by Boss (19.7k points)
+3

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

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

+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
answered by Active (4.6k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,775 questions
41,742 answers
118,910 comments
41,388 users