Mutual Asymptotic analysis of the given fucntions

Asked Dec 01 '14 at 08:57

Active Dec 01 '14 at 10:37

Viewed 32 times

$ f(n)$ = $ 3n^{\sqrt{n}} $

$g(n)$ = $2^{\sqrt{n}log_2n}$

$h(n)=n! $

For all the $3$ pairs of the functions, which one is $Big-O$ of which ?

I am unable to compare these functions.

Edit : I plotted them and observed that for large $n$ :- $h(n)>f(n)>g(n)$

edited Dec 01 '14 at 10:37

asked Dec 01 '14 at 08:57

PleaseHelp

1

Are you familiar with Stirling's formula for the factorial? [if not, look it up!] Can you simplify $2^{\log_2n}$? – Gerry Myerson Dec 01 '14 at 11:11
Ok. Let me study Stirling's formula. – PleaseHelp Dec 01 '14 at 11:27
1

So,$ g(n)$ = $ n^{\sqrt{n}}$ . – PleaseHelp Dec 01 '14 at 11:49
1

Right. So how do $f$ and $g$ compare? – Gerry Myerson Dec 01 '14 at 11:55
1

Both are Big-O of each other. – PleaseHelp Dec 01 '14 at 12:03
$ n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^{n}. $ Dividing by $ n^{\sqrt{n}}$ we get $\sqrt{2 \pi n}(\frac1 {e^n}) \left({n}{}\right)^{n-\sqrt{n}}$ which is greater than $1$ for large $n$ (HOW?). – PleaseHelp Dec 01 '14 at 12:03
@GerryMyerson can you help me a little more(:P) with my above comment ? – PleaseHelp Dec 01 '14 at 12:06
1

It might be easier to see what goes on if you look at the logarithm of, say, $g$ and of the approximation you found for the factorial. – Gerry Myerson Dec 01 '14 at 22:15
Good. Let me encourage you to write up what you know, and post it as an answer. – Gerry Myerson Dec 02 '14 at 11:11

0 Answers0