Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
technically, what you ask is not true for $n=0$... ;) otherwise beni said it all – Glougloubarbaki 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
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
up vote 4 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.