Hands-On Data Structures and Algorithms with JavaScript

Polynomial time complexity classes

Now that we have started this conversation, most of the time complexity types that we have discussed here so far are of the O(n^k) type, for example, it is a constant time complexity for n = 1, whereas it is quadratic complexity for k = 2.

The concept of polynomial time complexity leads us into a class of problems, which are defined based on the complexity of their solutions. The following are the types of classes:

• P: Any problem that can be solved in polynomial time O(n^k).
• NP: Any problem that can be verified in polynomial time. There can exist problems (such as sudoku solving) that can be solved in non-deterministic polynomial time. If the solution to these problems can be verified in polynomial time, ...