1
$\begingroup$

I'm using the limit definition to show that $f(n) \in\mathcal{O}(g(n))$ or the reverse for the following functions;

$f(n) = n^{1.000001}/\log n$

$g(n) = (1.000001)^n$

I calculated the limit as $\approx 0$ in Wolfram Alpha.

$$\lim_{ n \rightarrow \infty} f(n)/g(n) \approx 0, $$ and

$$\lim_{ n \rightarrow \infty} g(n)/f(n) \approx 0.$$

This is not right. How can I calculate the limits?

$\endgroup$
  • 2
    $\begingroup$ Numerically evaluating the ratio for small $n$ will fool you as $g(n)$ is much smaller than $f(n)$ untill $n \sim 10^7$. $\endgroup$ – Winther Oct 2 '18 at 11:00
2
$\begingroup$

Consider $1>a >0$, $f(x) = x^{1+a} /\log(x)$, $g(x)= (1+a)^x$. Then for every $x > 0$, $$ (1+a)^x = \mathrm e^{x \log(1+a)} = \sum_0^{+\infty} \frac {x^n \log(1+a)^n}{n!} > \frac {x^3 \log(1+a)^3}{6}, $$ then \begin{align*} 0 \leqslant \frac fg (x) &= \frac {x^{1+a}}{(1+a)^x \log(x)} \\&< \frac {6x^2}{x^3 \log(1+a)^3\log(x)} \\&<\frac 6{x \log(1+a)^3} \xrightarrow{x \to +\infty} 0, \end{align*} thus $f (x) \in O(g(x))$ as $x \to +\infty$, hence $f(n) \in O(g(n))$ as $\Bbb N^* \ni n \to \infty $.

For your question, it is simply the case $a = 10^{-6}$.

$\endgroup$
1
$\begingroup$

Use the standard limit $n^a/b^n\to 0$ as $n\to\infty$ for $b>1$. For your case $a=b=1.000001$ and thus the desired result is $0$.

$\endgroup$
  • $\begingroup$ short and simple. $\endgroup$ – kelalaka Oct 2 '18 at 11:58
0
$\begingroup$

I don't have time to write a full answer, sry :c this should help: https://en.m.wikipedia.org/wiki/L%27Hôpital%27s_rule

Try to rewrite your fraction and then use l'Hôpital! :)

$\endgroup$
  • $\begingroup$ This should be a comment, not an answer. $\endgroup$ – rtybase Oct 2 '18 at 11:17
  • $\begingroup$ ah yes, noted :) $\endgroup$ – C. Brendel Oct 2 '18 at 11:24
  • 1
    $\begingroup$ L'Hôpital rule would make the fraction much more complicated as I tried the calculation. This is not efficient at all. $\endgroup$ – xbh Oct 2 '18 at 11:37
  • 1
    $\begingroup$ if you use l'Hôpital on n¹⁰⁰⁰⁰⁰¹/1.000001ⁿ 2-times you are done! You just have to take the limit multiply that with te limit of 1/log(n). Did you differentiate log(n) in the denominator aswell? $\endgroup$ – C. Brendel Oct 2 '18 at 12: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.