Common classes of computational complexity

In this section, we will learn about some other common classes of computational complexity other than the constant, linear, quadratic, and suchlike complexities that have been discussed in the previous sections.

"Pretty well everybody outside the area of computer science thinks that if your program is running too slowly, what you need is a faster machine."

– Rod Downey and Mike Fellows

However, this is not the case, since some problems might require a brute-force search through a large class of cases that exponentially increases the number of steps required to solve the problem. An important distinction is often made between a tractable and intractable problem:

• Tractable problems make use of algorithms that take polynomial time (P) for their execution – time complexity is of the order O(nc), where c is any constant that belongs to the natural numbers.

  Feasibly decidable kinds of problems are problems...