Relations of some exponential functions -- which is correct?

Question

Consider the following functions

• $f(n) = 3n^{(n^{1/2})} $

• $g(n) = 2^{(n^{1/2}) \log n }$ // here base of $\log n$ is 2

• $h(n) = n !$

Which of the following is true?

1. $ h (n)$ is $O (f (n) ) $

2. $h (n)$ is $O (g (n)) $

3. $g (n)$ is not $O (f (n) ) $

4. $ f(n)$ is $O(g (n))$

I tried this way :

To check which function is large :

$3n^{(n^{1/2})}$ = taking log

$n^{1/2} \log 3n $

$g(n) = 2^{(n^{1/2}) \log n }$

by taking log :

$((n^{1/2})\log n )\log 2$ => $0.3 (n^{1/2})\log n $

$h(n) = n !$ => $n^n $

by taking log :

$n \log n $

So now comparing all these 3 functions I got following equality :

$f(n) < g(n) < h(n) $ So answer should be (4) but actually answer is (1).
Could anyone explain me where I am wrong ?

Answer 1

(1) is not the correct answer. Perhaps there is an error in the book, or an error in what you entered. As you correctly concluded, $f(n) = 3 e^{n^{1/2} \log n}$ and $h(n) \approx e^{n \log n}$ (by Stirling's approximation), so it is not true that $h(n) = O(f(n))$.

I can't tell whether you've drawn the correct conclusions about the pairwise relationships between these three functions. You wrote that $f(n) < g(n) < h(n)$, but this is not correct. For instance, $f(1) = 3$, $g(1) = 3$, $h(1) = 1$. Those inequalities don't hold for all $n$ -- but if we care about big-O notation, then that's not the right question anyway, since big-O notation relates to the asymptotic behavior of these functions (as $n\to \infty$).

The right question is whether $f(n) = O(g(n))$, whether $g(n) = O(f(n))$ (be careful here! better double-check your work on this one another time), and so on.

See also Sorting functions by asymptotic growth and How does one know which notation of time complexity analysis to use?. They should answer your remaining questions.