Computational Complexity


It is already discussed that decidable problems have algorithms. For solving a decidable problem, there may be more than one algorithm. The algorithms may differ in time taken and/or memory required to execute and produce the result, for the same input. This is known as computational complexity. It concerns with the question ‘which is the efficient algorithm for solving a decision problem.’ While discussing computational complexity, some underlying particulars such as hardware, software, and data structure are generally ignored. Computer science deals with the theoretical foundations of information, computation, and practical techniques for implementation and application. In this chapter, we shall discuss ...

Get Introduction to Automata Theory, Formal Languages and Computation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.