0
$\begingroup$

Sometimes you can substitute values for $n_0$ and $c$ in the big-$O$ equation and compare two functions. Or take limits and compare two functions.

But for the following functions, for example, taking the limit in infinity for $f_3$ over $f_2$ requires using l'Hôpital's rule which doesn't simplify anything. $f_3$ is technically the product of a polynomial and an exponential function. And I don't know how to go with comparing functions like that with others.

Firstly, I know that $f_4$ is the most efficient because it is $O(n^2)$. ($f_4(n) = n + \frac{n(n + 1)}{2}$) and the rest are exponential.

But for the rest, I really don't know what to besides using my intuition which could be really far from the correct answer anyway. Please help me compare these rigorously.

$f_1(n) = n^{\sqrt{n}}$

$f_2(n) = 2^n$

$f_3(n) = n^{100}2^{\frac{n}{2}}$

$f_4(n) = \Sigma_{i=1}^{n}i + 1$

Improve this question
$\endgroup$
2
  • $\begingroup$ $\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)$. $\endgroup$
    – plop
    Commented Sep 30, 2020 at 12:41
  • $\begingroup$ 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)$. $\endgroup$
    – plop
    Commented Sep 30, 2020 at 12:56

1 Answer 1

Reset to default
0
$\begingroup$

One useful technique for comparing functions asymptotically is to take their logs since doing that turns exponentials into polynomials. So, if you are comfortable with comparing polynomials, then taking logs is always something you should be thinking about.

There is one thing that you have to be careful of when you do that, however. After taking logs, you can not throw away constant factors anymore.

If you take the logs of your functions, you get $\log(f_1(n))=\sqrt{n}\log(n)$, $\log(f_2(n))=n\log(2)$ and $\log(f_3(n))= 100\log(n)+\frac{n}{2}\log(2)$. So, $f_2$ is asymptotically larger than $f_3$ which, in turn is asymptotically larger than $f_1$. You already know where $f_4$ goes.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! I've heard that there are only a few specific things that you could do. Like, take log. But you can't add powers or stuff like that. Where can I read more about what's allowed and what's not? $\endgroup$
    – Zara
    Commented Oct 1, 2020 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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