P refers to Polynomial, the complexity class of problems that are deemed to be tractable i.e. solved in worst-case polynomial time of or less. A P-class problem can be verified in polynomial time as well.
A P-Class problem will have the following Big-O time complexities:
- - Linear
- - Log
- - Loglinear
- - Polynomial
Examples
- Determining whether a number is prime
- All searches and sorts
- Matrix Multiplication