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$

1 Answer 1

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$
1
  • $\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
    Commented Aug 28, 2018 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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