Computer Science / Unit 3 CS 0161 short lesson, about 20 seconds
The Class P
Captions available
The idea
The polynomial time class, P, holds every problem with an algorithm whose runtime is a polynomial expression — O(1), O(log N), O(N), O(N log N), O(N squared) — the field's meaning of tractable.
In practice
Searching, sorting, hashing, traversal, spanning trees, shortest paths all ride here.
Where people slip
Polynomial is the boundary, not fast.
Your place on the trail
Every lesson rests on earlier ones and opens later ones. Tap any to jump.
Something wrong in this lesson? Flag it · Sources for Computer Science