1
$\begingroup$

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.

  • 7
    Well, you have, for $x$ large enough, $$e^{\sqrt{\log (x)}} \leq e^{log(x)}=x \leq x^n$$2011-11-22
  • 1
    technically, what you ask is not true for $n=0$... ;) otherwise beni said it all2011-11-22
  • 0
    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?2011-11-22
  • 0
    (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$2011-11-22
  • 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,2011-11-22
  • 0
    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.2011-11-22

1 Answers 1

5

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