O'Reilly logo

Introduction to Automata Theory, Formal Languages and Computation by Shyamalendu Kandar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

12

Computational Complexity

Introduction

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required