Course contentsShow
← Computer Science
Lesson 1890 of 2,87243. Complexity TheoryFree lesson

Examples of Problems in P

Examining concrete problems in P: sorting, shortest paths, matching, and their polynomial-time algorithms.

Examples of Problems in P

You'll learn: Which concrete computational problems can be solved efficiently in polynomial time and why they belong to the class P.

What Makes a Problem Easy?

Recall that P is the complexity class containing problems solvable by a deterministic algorithm in polynomial time—that is, in time proportional to n^k for some constant k, where n is the input size. Let's examine real problems that fit this definition.

Classic Problems in P

Sorting

Given a list of n numbers, arrange them in order. Algorithms like merge sort run in O(n log n) time, which is polynomial. Since we can always sort efficiently regardless of input size, sorting is in P.

Shortest Path

Finding the shortest path between two nodes in a weighted graph (Dijkstra's algorithm) runs in O(n² log n) time (or better with optimizations). Despite seeming complex, it's still polynomial—firmly in P.

Matching

Determining whether a bipartite graph has a perfect matching can be solved in O(n³) time using the Hungarian algorithm or similar approaches. Again, polynomial time = membership in P.

Other Examples

  • Linear programming (surprisingly!)
  • Primality testing (checking if a number is prime)
  • Graph connectivity (is the graph connected?)

Why This Matters

Think of P as the "tractable problems club"—problems we can realistically solve even as inputs grow large. A problem in P with n = 1,000,000 might take seconds or minutes, but it will finish. This distinguishes them from harder problems we'll encounter later.

Key Takeaway: Problems like sorting, shortest paths, and matching belong to P because we have polynomial-time algorithms for them, making them efficiently solvable in practice.