Karumanchi

Question

f(n)=$2^n$

g(n)=n!

h(n)=$n^{logn}$
 

which one is true?

A) f(n)=O(g(n)) and g(n)=O(h(n))

B) f(n)=$\Omega(g(n)))$ and g(n)=O(h(n))
C) g(n)=O(f(n)) and h(n)=O(f(n))

D) h(n)=O(f(n)) and g(n)=$\Omega(f(n))$

Comments

Option D, Take log of all the given function, asymptomatic order is h(n)<f(n)<g(n) ie  h(n) = O(f(n)) and O(g(n)) and g(n)=BigOmega(f(n)) and BigOmega(h(n))

---

Hint: The growth order is $n! > 2^{n} > n ^{\log(n)} $, see here https://www.desmos.com/calculator/clpuytfczj.

---

pls give a detailed solution. i'm unable to understand

---

Take two functions at a time, compare them by taking log and draw conclusion from them.

You will get f(n)<g(n), h(n)<g(n) and h(n)<f(n) . So, the answer is (d).

---

https://www.cs.nmsu.edu/~ipivkina/Fall08cs372/Fall05/asympNot.pdf