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.

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