Key Sequence
New Concepts
Important Results / Claims
- space complexity is tricky…
- “gold standard” for space complexity is \(O\qty(\log\qty(n))\)
- \(\text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(t\qty(n))\)
- \(\text{SPACE} \qty(s \qty(n)) \subseteq \text{TIME}\qty(2^{O\qty(s\qty(n))})\)
- space hierarchy theorem
- Space Time Hierachy