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