I have a book which includes the following two statements:
Theorem 1: There exists a family of languages recognizable by an type A automata of size $O(n)$ such that any equivalent type B automaton must be of size $n!$ or larger.
$\dots$
Theorem 2: We can convert a type A automaton with $n$ states into a type B automaton with $2^{O(n \times \log n)}$ states. This conversion is optimal, see Theorem 1.
In the derivation of the complexity $log$ refers to the binary logarithm, i.e. base $2$.
Now I'm really not sure about this at multiple places.
First of all, I'm not really confident with the $O$-notation inside a function. Purely sytactical it makes no sense to raise a number to the power of a set. So how exactly is this to be understood?
Then I'm also a bit confused about the way theorem 1 is phrased because the type A automaton's size is given with the asymptotic notation whereas the type B automaton's size is given as a set function whereas in Theorem 2 it's the other way around.
Now diving into the functions themselves, I'm aware that $O(\log n)$ does not depend on the base of the $\log$, i.e. in my case $n \log_2n \in O(n \log n)$ and also $n \log_4n \in O(n \log n)$. Plugging these into the complexity given (as I'd understand the notation):
$2^{nlog_2n} = n^n$
$2^{nlog_4n} = n^{n/2}$
should both be in $2^{O(n \times \log n)}$
But then $n^n$ is faster growing than $n!$ whereas $n^{n/2}$ is not.
For the proof to make any sense I'd expect $n! = 2^{O(n \times \log n)}$ but right now I don't see how that's the case...
Hopefully someone can shed a bit of light on how the $O$-notation inside a function can be understood and on how these complexities compare.
Using $f\ll g$ as an abbreviation for $f\in o(g)$,$$2^{n\ln n}\ll n!\sim\sqrt{2\pi n}n^ne^{-n}\ll n^n=e^{n\ln n},$$where the first $\ll$ follows from comparing $\ln(2^{n\ln n})=n\ln n\ln 2$ with $\ln(\sqrt{2\pi n}n^ne^{-n})\sim n\ln n$.