Time Complexity Homework
- Sipser exercise 7.1
- If a multi-tape Turing machine can decide a certain language in \(O(n^2)\) time, what would be the time complexity of simulating the same algorithm on a single tape Turing machine?
- What is the time complexity of the Turing machine in example 3.7 in the book? Use big-\(O\) notation and show your work.
- What is the time complexity of the Turing machine in example 3.11 in the book? Use big-\(O\) notation and show your work.
- What is the time complexity of the Turing machine in example 3.12 in the book? Use big-\(O\) notation and show your work.