# Relations of some exponential functions — which is correct?

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 ?

• The answer given in the book could be wrong. – Yuval Filmus Jul 31 '13 at 18:47
• This question should contain all you need. – Raphael Aug 1 '13 at 8:57

(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.