Timeline for Comparing the big-$O$ of these four functions

6 events

when toggle format	what		by	license	comment
Oct 1, 2020 at 13:13	vote	accept	Zara
Sep 30, 2020 at 14:58	answer	added	mursalin		timeline score: 0
Sep 30, 2020 at 12:56	comment	added	plop		To compare $f_1$ and $f_2$ maybe compare $g_1(n)=\log(f_1(n))=n^{1/2}\log(n)$ and $g_2(n)=\log(f_2(n))=n\log(2)$. If, for example, you do $\frac{g_1}{g_2}(n)=\frac{\log(n)}{n^{1/2}\log(2)}$. Using L'Hospital as before, you get to consider the limit of $\frac{1/x}{\frac{1}{2}\log(2)x^{-1/2}}=2(\log(2))^{-1}x^{-1/2}\to0$ as $x\to+\infty$. Therefore, there is some $n_0$ such that for all $n\geq n_0$ we have $g_1(n)\leq g_2(n)$. Applying $e^x$, which is increasing, on both sides we get that $f_1(n)\leq f_2(n)$, for all $n\geq n_0$. So, $f_1\in O(f_2)$.
Sep 30, 2020 at 12:41	comment	added	plop		$\frac{f_3}{f_2}(n)=\frac{n^{100}}{(2^{1/2})^n}$. If you consider the corresponding function over the reals and do L'Hospital you would have to consider the quotient $\frac{100x^{99}}{(2^{1/2})^x\log(2^{1/2})}$. The degree of the polynomial in the numerator decreased. You can apply L'Hospital $99$ more times to get to $\frac{100!}{(2^{1/2})^x(\log(2^{1/2}))^{100}}$. This tends to $0$ as $x\to+\infty$. So, $f_3\in O(f_2)$.
Sep 30, 2020 at 10:43	review	First posts
Oct 3, 2020 at 16:31
Sep 30, 2020 at 10:34	history	asked	Zara	CC BY-SA 4.0