1
$\begingroup$

For the two functions $f(n)=n^{100}$ and $g(n)=2^{n/100}$, I am trying to determine whether $f(n) = O(g(n))$. In order to do this, I used L'Hopital's rule as if $\lim\limits_{n\to\infty} \frac{f(n)}{g(n)}=0$, this implies that eventually $f(n) < g(n)$, and thus $f(n) = O(g(n))$.

As the following limit is of indeterminate form, L'Hopital's rule can be used: $$\lim_{n\to\infty} \frac{f(n)}{g(n)} = \frac{\infty}{\infty}$$

However, when I tried using L'Hopital's rule using the derivatives of $f(n)$ and $g(n)$ with respect to $n$, the limit is of indeterminate form: $$\lim_{n\to\infty} {100n^{99}\over 2^{n/100-2}\cdot \ln2/25} = \frac{\infty}{\infty}$$

Is there any other method I can use to demonstrate the $f(n) = O(g(n))$, since using L'Hopital's rule did not work. Any insights are appreciated.

$\endgroup$
  • $\begingroup$ Notice that your limit is still in the indeterminate form $\infty / \infty$, and you can get your limit by repeatedly using L'Hopital. $\endgroup$ – Hyperion Mar 10 at 23:04
  • $\begingroup$ So can I use it on the expression f''(n)/g''(n), and so on, until I get a definite answer? $\endgroup$ – ceno980 Mar 10 at 23:06
  • $\begingroup$ If your limit is still in the form $\infty/\infty$ meets all the criterion for applying L'Hopital, you can use it as many times as you find necessary. So yes. $\endgroup$ – Hyperion Mar 10 at 23:07
  • $\begingroup$ @ceno980. Yes, 99 times. $\endgroup$ – William Elliot Mar 10 at 23:10
  • $\begingroup$ I don't think L'Hopital's rule will be the best way to approach this problem. $\endgroup$ – ceno980 Mar 10 at 23:11
1
$\begingroup$

Nor mally you shouldn't even think of L'Hospital? It is a basic result that for any $\alpha, \beta>0$, one has $$x^\alpha =o(\mathrm e^{\beta x}) \quad(x\to+\infty),\;\text{ which means }\lim_{x\to+\infty}\frac{x^\alpha}{\mathrm e^{\beta x}}=0.$$ Now, note that $2^{n/100}=\mathrm e^{\ln 2\cdot n/100}$.

$\endgroup$
  • $\begingroup$ What does o(e^βx) mean? Thanks. $\endgroup$ – ceno980 Mar 10 at 23:14
  • $\begingroup$ It means what I wrote at the end of the equation. $\endgroup$ – Bernard Mar 10 at 23:19
  • $\begingroup$ What does the o in o(e^βx) specifically mean? $\endgroup$ – ceno980 Mar 10 at 23:24
  • $\begingroup$ For me it's only a notation introduced by Edmund Landau for a class of functions at the beginning of the 20th century. It reads as ‘little oh’. $\endgroup$ – Bernard Mar 10 at 23:34
  • $\begingroup$ Would it be possible to know how the above result was derived? E.g. Is there a proof for it? $\endgroup$ – ceno980 Mar 10 at 23:42
0
$\begingroup$

We have $\log\left(n^{100}\right)=100\log(n)$ and $\log\left(2^{n/100}\right)=\frac{\log(2)}{100}n$. Both of these tend to $\infty$. Applying L'Hopital to the logs gives $$ \begin{align} \lim_{n\to\infty}\frac{100\log(n)}{\frac{\log(2)}{100}n} &=\lim_{n\to\infty}\frac{100\frac1n}{\frac{\log(2)}{100}}\\ &=0 \end{align} $$

$\endgroup$
  • $\begingroup$ Is the answer valid if you apply L'Hopital's rule to log(f(n)) and log(g(n))? I heard that when trying to demonstrate that f(n) is O(g(n)) you can't use the logs of f(n) and g(n) since f(n) ≠ log(f(n)). $\endgroup$ – ceno980 Mar 10 at 23:54
  • $\begingroup$ If $\lim\limits_{n\to\infty}g(n)=\infty$ and $\lim\limits_{n\to\infty}\frac{\log(f(n))}{\log(g(n))}=0$, then for $n$ large enough, $\frac{\log(f(n))}{\log(g(n))}\le\frac12$, so $\frac{f(n)}{g(n)}\le\frac1{\sqrt{g(n)}}\to0$. $\endgroup$ – robjohn Mar 11 at 1:25
  • $\begingroup$ For the OP: the key requirement here for algebraic manipulation is that the inverse of $\log$ is non-decreasing. This gives a theorem more general than for just $\log$s. $\endgroup$ – adfriedman Mar 11 at 8:00

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.