Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Consider $$ \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE}(2^{c (\log{n})^2}) \quad \overset{?}{=} \quad \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE} ( n^{c \log{n}})$$
My lecture notes say that this is an equality, can someone point me to the theorem (or explain) why this is ?
I've observed that one power of the logarithm in the exponent disappeared but I couldnt find a theorem resembling any of the above.
Suppose first that $\log n$ stands for base 2 logarithm. In this case, since $n = 2^{\log n}$, we have $$ 2^{c\log^2 n} = (2^{\log n})^{c\log n} = n^{c \log n}, $$ from which your identity immediately follows.
If $\log n$ uses some other base, we still get the same result, because both sides of the identity are insensitive to the base of the logarithm. This is because different logarithms differ by a constant factor, and this constant factor can be swallowed by the union over $c$. Details left to you.
