geeksforgeeks

Question

Which of the following is true? (GATE CS 2000)

(a) h(n) is 0(f(n))
(b) h(n) is 0(g(n))
(c) g(n) is not 0(f(n))
(d) f(n) is 0(g(n))

Answer 1

Answer: Option (D)

Here g(n) = 2*n^{$^{\sqrt{n}}$ .}  

(Just Simplify it)

So, we can say that f(n) $\equiv$ g(n) .

And thus first two options are Wrong as h(n) = nⁿ    (Just represented in different Form)

This means option D is right Only.

Comments

not a very clear explanation

---

See, f(n) = 3n^n√n .

and   g(n) = 2n^n√n .

So  we can say that f(n) and g(n) both will rise on the same rate. And we can represent them as f(n) =g(n) = k*n^n√n . where k is Const.  

And h(n) = n! that is nearly equal to nⁿ . For such a big n. 

Now , see only Option D satisfies the Relations.

Tell me If you are getting this or not!!!

Answer 2

Answer is D.

Solution:. Simplify the functions by taking logarithm of each function:

log(f(n)) = ( sqrt n) log (base 3) n

log(g(n)) = (sqrt n) log (base 2) n

log(h(n)) = log (n!). But according to Stirling's approximation n! = O(n^n)

So, log(h(n)) = n log n

 

Hence, we can see that log(f(n))= log(g(n)) < log(h(n)). (asymptotically)

It implies f(n) = g(n) < h(n)

The only option that satisfies this is option D which says f(n) = O(g(n)) which is true because f(n) = Theta( g(n))