Algorithms for Smart World Technologies

Chapter 2Computational Complexity

Any computation requires energy, which directly corresponds to the system resources consumed during the process. In computing, these resources are referred to as system resources, with the most essential being the processor and memory—since computation involves both executing instructions and storing intermediate results. The computational complexity of an algorithm, often referred to simply as its complexity, measures the amount of these resources needed for execution, with primary emphasis on time and memory usage.

This chapter explores the concept of computational machines and evaluates their efficiency. It then introduces the principles of amortized analysis and discusses the significance of recurrence relations in analyzing algorithms.

After reading this, readers will gain a clear knowledge of computational complexity, including a detailed demonstrations of the following:

• Theoretical Frameworks for Computation: Formalization of computational problems, the nature of decision problems, and detailed discussions of computational models such as deterministic and nondeterministic Turing machines.
• Complexity Classes and Their Relationships: An exploration of complexity classes such as P (polynomial time), NP (nondeterministic polynomial time), PSPACE (polynomial space), EXP (exponential time), BPP (bounded-error probabilistic polynomial time), and BQP (bounded-error quantum polynomial time), highlighting their inclusion and exclusion relationships, ...