Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

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.