Exponential and factorial that grow at exactly the same rate I want to find a relation of the form 
$$
n^{n^a} = \Theta (n!)
$$
I know and can reason fairly easily that $n^n$, where $a=1$, grows faster than $n!$, and $n^{\sqrt{n}}$, where $a=\frac{1}{2}$, grows more slowly than $n!$, so we can state the bound: $$\frac{1}{2} < a < 1$$  However, there appears to be no value in the bound, even in the limit as $a$ approaches $1$, that can make the exponential grow at exactly the same rate as the factorial.  Is there no way to satisfy the above expression (in which case, why?), or have I missed something fairly obvious?
 A: Finally I found some time to expand my comments into a complete answer. I hope this can give you further intuition.

Factorials and powers
A well-known approximation of $n!$ is given by Stirling's formula:
$$n!\sim \sqrt{2\pi n}\left(\frac ne\right)^n.$$
We can write the right side as
$$\sqrt{2\pi}\cdot \underbrace{n^{n+1/2-n\log_n(e)}}_{:=\,g(n)}$$
This means, that the best approximation of $n!$ of the form $n^{f(n)}$ is $g\in\Theta(n!)$. More precisely $n!/g(n)\to\sqrt{2\pi}$. Since $f(n)=n+1/2-n\log_n(e)$ is not of the form $n^a$, there is no best value $a$ for this approximation desprite maybe $a=1$ since $f\in\Theta(n^1)$.
Always keep in mind that the Landau notation $\Theta$ (and the related big- and small-O's) are just one way to classify function growth (a very useful one in reality though).

Function growth and hyperreals
You understandably wonder about how it can be that just going from $n^1$ to any $n^a,a>1$ suddenly changes the relation between $n!$ and $n^{n^a}$. Shouldn't there be some value $a$ which we can approximate, e.g. with binary search $-$ always checking whether $n^{n^a}$ is finally bigger or smaller than $n!$ and then adjust $a$ a bit?
Qiaochu gave another example: the function $n\log (n)$ is not in any $\Theta(n^a)$ for any $a\in\Bbb R$. So you can find this effect for simpler functions too.
Here is a reasoning on some other basis. Think of the powers $n^a$ as too coarsaly distributed in the set of all functions. I mean that from the point of view of all functions, there are huge gaps between $n^1$ and $n^a$ for any $a>1$. And these gaps are filled with other functions, e.g. $n\log(n)$. Here are some analogies  which try to mimic this effect with numbers:


*

*The set of integers is "coarse" in $\Bbb R$. When you try to approximate $1/2$ using whole numbers, you try $...,-2,-1,0<1/2$ and then "suddenly" the next plausible value $1$ is already above $1/2$.

*The above example might be not so really satisfying since $\Bbb Z$ is too discrete in some sense compared to $\Bbb R$. Try it with $\Bbb Q$ and approximating $\sqrt 2\in\Bbb R$. Any rational number is either below or above $\sqrt 2$.

*This example might still be unsatisfying since there is no "next" value $q\in\Bbb Q$ which suddenly is above $\sqrt 2$. It is more that we never reach $\sqrt 2$ in the first place. Also, the powers $n^a$ are parametrized by a real value $\Bbb R$ and we can hardly imagine that the reals are "too coarse" for parametrizing something. Let me introduce the hyperreal numbers $\Bbb R^*$. They are essentially the reals $\Bbb R$ enriched by infinite numbers (say $\omega$) and infinitesimal (i.e. infinitely small) numbers (say $\epsilon$). We are interested in the infinitesimal number $\epsilon$ which is bigger than $0$ but smaller than any real number $a>0$, i.e.
$$0<\epsilon<a,\quad\forall a\in\Bbb R,a>0.$$
Now try to approximate $\epsilon$ with real numbers. Any $a>0$ is too big. No matter how close we approach zero with $a$, we are still above. But then suddenly as we jump to zero, we are below $\epsilon$. So this resembles this exact effect we observed for functions. The reals $\Bbb R$ are "too coarsely distributed" inside the hyperreals $\Bbb R^*$. There is a huge gap between $0$ and any real number $a>0$ which is filled by infinitesimals like $\epsilon,\epsilon^2$ or $\epsilon/2$. You can think of the function $n^{n^a}$ as the hyperreal number $a\in\Bbb R^*$ and $n!$ as the hyperreal number $1+\epsilon$. By the way, usually the hyperreal numbers are exactly constructed by observing this exact phenomenon that you found here. So they are somehow made to resemble this effect.

