2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I already started to wonder how I could apply savich's theorem, but this is much clearer, thanks for taking the time and explaining in such detail. accepted ! $\endgroup$ – zython Aug 28 '18 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.