2

I have to prove the following:

Let $n \in \mathbb{N}$. Proove:

$$e^{\sqrt{\log x}}=O(x^n) .$$

I just know the definition of $O$:

$f(x), g(x)$ are real functions. $f(x)=O(g(x))$ means, that for large $x$, $|f(x)| \leq C \cdot g(x)$ holds.

I'm a little bit confused, because I thought $O$ is part of the analysis and not number theory (in analysis I used it for Taylor series). Anyone can give me a hint where to start (or show an other example?). Best regards.

Srivatsan
  • 26,311
ulead86
  • 3,381
  • 9
    Well, you have, for $x$ large enough, $$e^{\sqrt{\log (x)}} \leq e^{log(x)}=x \leq x^n$$ – Beni Bogosel Nov 22 '11 at 18:26
  • 1
    technically, what you ask is not true for $n=0$... ;) otherwise beni said it all – Albert Nov 22 '11 at 18:28
  • Ah forgot to mension, that x is a large number... Sorry (I edited it). Perhaps you post it as an answer? and is the $p(x)=O(x^n)$ (p(x) is a real polynom of degree n) nearly the same? – ulead86 Nov 22 '11 at 18:42
  • (it's an other proof) so I post my answer here: Show $p(x)=O(x)$. So I have to show $\left|p(x)\right| \leq x^n * C$. $p(x)=a_0+a_1 x+...+a_n x^n \leq a_n x^n = C * x^n$ – ulead86 Nov 22 '11 at 18:49
  • 1
    Dear Daniel, Regarding your statement "I'm a little bit confused": analyzing the order of growth of various functions related to arithmetic is one of the basic topics of analytic number theory. In order to do this, you have to have (at minimum) a good feeling for the order of growth of various classical functions (such as $e^{\sqrt{\log x}}$). Regards, – Matt E Nov 22 '11 at 19:44
  • It is certainly not true, in general, that $a_0+a_1x+\cdots+a_nx^n\le a_nx^n$. But you can prove that for every $j\lt n$ there's an $N_j$ such that $x\gt N_j$ implies $a_jx^j\lt x^n$, and then take it from there. – Gerry Myerson Nov 22 '11 at 22:26

1 Answers1

7

I'll write my comment as an answer, as some other comments suggested.

We have the following inequalities for $x$ large enough and for $n \geq 1$:

$$ e^{\sqrt{\ln x}} \leq e^{\ln x}=x \leq x^n$$

This means by definition that $e^{\sqrt{\ln x}} = O(x^n)$.

Beni Bogosel
  • 23,381