# Effect of determinization on the time complexity of Turing machines

Suppose I assume that the complexity of a non-deterministic Turing machine $$N$$ is $$T(n)$$, $$n$$ is the length of the input string. What would be the time complexity of a deterministic Turing machine $$D$$ equivalent to $$N$$?

• That depends on $N$. For the worst case, you might want to check e.g. the Exponential Time Hypothesis. There is not a strong theorem like Savitch's Teorem for space complexity, establishing a similar tight connection. – ttnick Apr 16 at 17:42
• How do you construct $D$ from $N$? – Yuval Filmus Apr 19 at 5:57