When we studied decidability and undecidability, there was no concern about the TM’s computation tape or the number of cells used. In computational complexity theory, which we begin exploring in this chapter, we are concerned with the resources TMs use in making their decisions. This concern is because a problem is decidable and requires an astronomical amount of resources, which is practically unsolvable. To address this concern, computational complexity theory uses time and space measures and uses the measures to compare algorithms that are run on TMs. In this chapter, we study the basic concepts of the complexity theory.