0
$\begingroup$

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 ?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.