# Comparing the growth rate of two functions using L'Hopital's rule

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.

• Notice that your limit is still in the indeterminate form $\infty / \infty$, and you can get your limit by repeatedly using L'Hopital. – Hyperion Mar 10 at 23:04
• So can I use it on the expression f''(n)/g''(n), and so on, until I get a definite answer? – ceno980 Mar 10 at 23:06
• 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. – Hyperion Mar 10 at 23:07
• @ceno980. Yes, 99 times. – William Elliot Mar 10 at 23:10
• I don't think L'Hopital's rule will be the best way to approach this problem. – ceno980 Mar 10 at 23:11

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}$$.

• What does o(e^βx) mean? Thanks. – ceno980 Mar 10 at 23:14
• It means what I wrote at the end of the equation. – Bernard Mar 10 at 23:19
• What does the o in o(e^βx) specifically mean? – ceno980 Mar 10 at 23:24
• 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’. – Bernard Mar 10 at 23:34
• Would it be possible to know how the above result was derived? E.g. Is there a proof for it? – ceno980 Mar 10 at 23:42

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}

• 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)). – ceno980 Mar 10 at 23:54
• 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$. – robjohn Mar 11 at 1:25
• 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. – adfriedman Mar 11 at 8:00