# Breakdown of the Space Hierarchy Theorem

Say that we have two deterministic space complexity classes $$SPACE(n^k)$$ and $$SPACE(f(n))$$ where $$f(n) = n^{k-1}$$ when $$n$$ is odd and $$f(n) = n^{k+1}$$ when $$n$$ is even. Obviously, if $$f(n)$$ were always $$n^{k+1}$$, we would able to say $$SPACE(n^k) \subseteq SPACE(f(n))$$ by the Space Hierarchy Theorem, and I believe that as $$n$$ grows we can still generally say $$SPACE(n^k) \subseteq SPACE(f(n))$$ (correct me if I'm wrong), but given the condition when $$n$$ is odd, do we just have to say that always $$SPACE(n^k) \neq SPACE(f(n))$$?

Suppose that $$f(n) \geq \log n$$ is space-constructible, that $$g(n) = o(f(n))$$, and that $$h(n) = g(n)$$ infinitely often (that is, for infinitely many $$n$$). Then $$\mathrm{SPACE}(f(n)) \not\subseteq \mathrm{SPACE}(h(n))$$.
Here $$\mathrm{SPACE}(f(n))$$ consists of all languages decided by multi-tape Turing machines which use $$O(f(n))$$ space.
Proof. We closely follow the Wikipedia proof of the space hierarchy theorem. Let $$L = \{ (\langle M \rangle, 1^m) : \text{when M is run on x = (\langle M \rangle, 1^m), it uses \le f(|x|) space and rejects} \}$$ Here $$1^m$$ is just $$1$$ repeated $$n$$ times, and we encode the input such that its size is exactly $$C_M + m$$, for some constant $$C_M$$ depending only on $$M$$.
The language $$L$$ is clearly in $$\mathrm{SPACE}(f(n))$$. Suppose that it is also in $$\mathrm{SPACE}(h(n))$$, say accepted by a machine $$M$$ which uses space $$Ch(n)$$. Since there are infinitely many $$n$$ such that $$h(n) = g(n)$$ and $$g(n) = o(f(n))$$, we can find $$m$$ such that $$Ch(C_M + m) = Cg(C_M + m) \leq f(C_M + m)$$. When running $$M$$ on $$x = (\langle M \rangle, 1^m)$$, it uses at most $$Ch(|x|) = Cg(|x|) \leq f(|x|)$$, and so $$(\langle M \rangle, 1^m) \in L$$ iff $$M$$ doesn't accept $$(\langle M \rangle, 1^m)$$, contradicting the assumption that $$M$$ computes $$L$$. $$\square$$
Using this, you can check that $$\mathrm{SPACE}(n^k)$$ and $$\mathrm{SPACE}(f(n))$$, where $$f(n)$$ is the function defined in your post, are incomparable: none is contained in the other.