Is $x^x$ in the same asymptotic growth class as an exponential function?

Question

I see that for any natural number $a$, $\lim_{x\to\infty} \tfrac{x^x}{a^x}$ approaches $\infty$, so the limit does not exist. So is this function have a different big-O than $O(a^x)$, for example? So what are the complexity classes beyond exponential time like this, if it's not factorial?

Answer 1

For large $x$, no question of what to do with $0^0$ arises and we may write $x^x = \mathrm{e}^{x \ln x}$ and $a^x = \mathrm{e}^{x \ln a}$. Note that $x \ln x$ always out-grows $x \ln a$, so there is no $a$ such that $x^x \in O(a^x)$.

(In fact, your observation about the infinite limit is sufficient to establish this.)

However, $x^x = \mathrm{e}^{x \ln x} \in O(\mathrm{e}^{x^2})$...