ABSTRACT

The word complexity in the theory of computation is probably due to the inherent difficulty in a computational problem. This theory is important to study the behavior of the problems and to quantify the amount of resources such as time and storage needed to solve them. This chapter presents only the formal definitions of some complexity classes. For details about the complexity theory and complexity classes, the reader may refer to some standard books on complexity theory. The big-O notation gives an upper bound on the growth rate of a function. The running time of an algorithm is defined in best case, worst-case, and average-case. Running time of any algorithm depends on the size of the input of the algorithm. The expression in the probability bound is for a correct recognition of an instance.