NSPACE can also be used to determine the time complexity of a deterministic Turing machine by the following theorem:
If a language L is decided in space S(n) (where S(n) ≥ log n) by a non-deterministic TM, then there exists a constant C such that L is decided in time O(CS(n)) by a deterministic one.[2]
Limitations
The measure of space complexity in terms of DSPACE is useful because it represents the total amount of memory that an actual computer would need to solve a given computational problem with a given algorithm. The reason is that DSPACE describes the space complexity used by deterministic Turing machines, which can represent actual computers. On the other hand, NSPACE describes the space complexity of non-deterministic Turing machines, which are not useful when trying to represent actual computers. For this reason, NSPACE is limited in its usefulness to real-world applications.