P

P refers to Polynomial, the complexity class of problems that are deemed to be tractable i.e. solved in worst-case polynomial time of $O(n^c)$ 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:

• $O(n)$ - Linear
• $O(log(n))$ - Log
• $O(n\ast log(n))$ - Loglinear
• $O(n^c)$ - Polynomial

Examples §

• Determining whether a number is prime
• All searches and sorts
• Matrix Multiplication