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$
1
  • 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, 2018 at 11:00

3 Answers 3

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$
1
  • $\begingroup$ short and simple. $\endgroup$
    – kelalaka
    Oct 2, 2018 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$
4
  • $\begingroup$ This should be a comment, not an answer. $\endgroup$
    – rtybase
    Oct 2, 2018 at 11:17
  • $\begingroup$ ah yes, noted :) $\endgroup$
    – C. Brendel
    Oct 2, 2018 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, 2018 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, 2018 at 12:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .