4

I was graphing $n^{0.01}$ for huge values of $n$ and noticed this function grows incredibly slow, much slower then $\log(n)$ it appeared from the graph. So my initial thought was that

$$n^{0.01}\in\mathcal O(\log(n))$$

$$\log^x(n)\in \mathcal O(n^y)$$

for any fixed constant $x > 0$ and $y > 0$, which made me think my initial thought was wrong. enter image description here

T-bone's House
  • 63
  • 2
  • 8
  • 1
    $$lim_{n\to\infty}\frac{n^{0.01}}{\log n}=\infty$$ – Ian Miller Jan 12 '17 at 01:21
  • Powers always grow faster than logarithms, for $n$ sufficiently large. – Michael Burr Jan 12 '17 at 01:21
  • Try plotting it on a graph, I am looking at my graph, and unless I am doing something wrong, which wouldn't be the first time, looks like at $$10^{42}$$ seems to me that $$log(n)$$ still grows much faster, (i'd post an image of the graph I don't have high enough reputation) – T-bone's House Jan 12 '17 at 01:29
  • I believe you guys though, I just am having trouble seeing it based off the graphs http://imgur.com/a/xU8TT – T-bone's House Jan 12 '17 at 01:35
  • @T-bone'sHouse You just aren't graphing it far enough (and maybe it isn't practical to do so with a generic graphing utility). If you take $n = 10^{1000}$ it is easy to compute that $n^{0.01} = 10^{10}$, but $\log(n) = 1000 \log 10$ which is much smaller than $10^{10}$. Now imagine taking $n=10^{1000000}$... – Erick Wong Jan 12 '17 at 01:48
  • @ErickWong Thanks, I see it now. – T-bone's House Jan 12 '17 at 01:52
  • $ (\log x)/x\to 0$ as $x\to \infty .$ And for fixed $ k >0$ and for $x>0$ we have: $ x^k\to \infty \iff x\to \infty ,$ so $(\log x)/x^k=(1/k) (\log x^k)/x^k \to 0$ as $x^k\to \infty$, equivalently, as $ x\to \infty.$ – DanielWainfleet Jan 12 '17 at 01:56
  • @T-bone'sHouse, you can always put the image in your original question – Travis Jan 12 '17 at 02:00
  • @Travis now that I have enough reputation I am able to but before it was impossible, guarantee it wouldn't make that up – T-bone's House Jan 12 '17 at 02:09
  • $n^{0.01}$ catches up to $\ln n$ at around $n=10^{280}$ (Rough calculation ). – DanielWainfleet Jan 12 '17 at 02:10
  • @IanMiller I know this is a really basic calc question but how would I go about showing that? You don't have to do it, but just point me in the right direction – T-bone's House Jan 12 '17 at 02:11
  • Sorry. $\approx10^{42}$ was were the rate of change of the growth of $n^{0.01}$ overtakes $\log n$. – Ian Miller Jan 12 '17 at 02:16

3 Answers3

2

It is enough to take the limit $\frac{n^{\alpha}}{\log n}$ with $\alpha >0$ to see that it tends to infinity and hence we get a stronger relation: $n^{\alpha} = \omega (\log n)$. In other words, the ratio is not bounded above by any constant.

Alex
  • 19,262
2

To show that $\lim_{n\to\infty} \frac{n^a}{\log n}=\infty$ you can apply L'Hopital.

$$\lim_{n\to\infty}\frac{n^a}{\log n}=\lim_{n_\infty}\frac{a\cdot n^{a-1}}{\frac{1}{n}}=\lim_{n\to\infty}a\cdot n^a=\infty\ (\because a>0)$$

Ian Miller
  • 11,844
1

How about this: Let $x_1 = 10^{1000}$ and $x_2 = 10^{2000}$. Then, assuming $\log$ is the base-10 logarithm,

$$\log(x_1) = 1000 \quad\text{and}\quad \log(x_2) = 2000.$$

From $x_1$ to $x_2$, $\log(x)$ increases by $1000$. However, $x_1^{0.01} = 10^{10}$ and $x_2^{0.01} = 10^{20}$. The difference between $10^{10}$ and $10^{20}$ is clearly greater than $2000$. So, at least here, we can see $n^{0.01}$ growing faster than $\log$.

Enrico Borba
  • 782