# O notation and growth order of function

This is for a homework problem, and I was wondering if someone could check my work and conclusions about growth of a function

I am trying to determine if the following formula is Polynomial? Superpolynomial? Exponential?

$$f(n) = 2^{\sqrt{2log(n)}}$$

### Polynomial Work

In order to determine if an equation is Polynomial it must be $f(n)=O(n^b)$ for some $b > 1$ which would mean that $|2^{\sqrt{2log(n)}}| \leq C*|n^b|$ for some $C > 0$ and some $k \geq 0$ and some $b > 1$ where $n \geq k$.

I think this means that if the above was true then $\lim_{n\to\infty}\frac{n^b}{2^{\sqrt{2log(n)}}} = \infty$ for some b > 0 because $n^b$ has a greater order than growth than $f(n)$ and $n^b$ would be an upper bounds of $f(n)$. However I do not think it is true because at a glance $f(n)$ looks to me like it is $O(b^n)$ which has a greater order of growth than $n^b$ so it is not Polynomial.

### Superpolynomial Work

In order to determine if an equation is Superpolynomial it must be $f(n)=\Omega(n^k)$ for every k which would mean that $|2^{\sqrt{2log(n)}}| \geq C*|n^k|$ for some $C > 0$ and some $k \geq 0$ where $n \geq k$.

I think this means that if the above was true then $\lim_{n\to\infty}\frac{n^k}{2^{\sqrt{2log(n)}}} = 0$ because $f(n)$ has a greater order than growth than $n^k$ and $n^k$ would be an lower bounds of $f(n)$. However I do not think it is true because at a glance $f(n)$ looks to me like it is $O(b^n)$ which has a lesser order of growth than $n^k$ so it is not Superpolynomial.

### Exponential Work

In order to determine if an equation is Exponential it must be $f(n)=\Omega(b^n)$ for some $b > 1$ which would mean that $|2^{\sqrt{2log(n)}}| \geq C*|b^n|$ for some $C > 0$ and some $k \geq 0$ and some $b > 1$ where $n \geq k$.

I think this means that if the above was true then $\lim_{n\to\infty}\frac{b^n}{2^{\sqrt{2log(n)}}} = 0$ for some $b > 0$ because $f(n)$ has a greater order than growth than $b^n$ and $b^n$ would be an lower bounds of $f(n)$. However I do not think it is true because although at a glance $f(n)$ had looked to me like it is $O(b^n)$ which is the same as the growth order of $b^n$, I know that is is actually more like $O(b^{log(n)})$. Since $n > log(n)$, $b^n$ has a greater order of growth than $f(n)$ so it is not Exponential.

-

Indeed $f(n)\ll n$, that is, $\lim\limits_{n\to\infty}g(n)=+\infty$ with $g(n)=2^{-\sqrt{2\log n}}n$. In particular, $f(n)=O(n)$ (and in fact, $f(n)=O(n^b)$ for every $b\gt0$).
To show this, note that $\log g(n)=\log n-c\sqrt{\log n}$ for some $c$, hence $\log g(n)\to+\infty$.