Chapter 12. Time and Space Complexity
In the earlier chapters, we considered the Turing machine (TM) and its acceptance power. By Church–Turing hypothesis, we realize that whatever could be done by a computer can be achieved by a TM. Also, while considering the variations of TMs, we found that even though all of them have the same accepting power, the number of steps could be very much increased in some cases. We also noted earlier that a procedure corresponds to a TM and an algorithm corresponds to a TM, which halts on all inputs. When we study algorithms for problems, we are also interested in finding efficient algorithms. Hence, it becomes essential to study the time and tape (space) complexity of TMs. In this chapter, we study some of these ...
Get Introduction to Formal Languages, Automata Theory and Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
