Beyond Polynomial Time: Exponential Growth & a Taste of P vs. NP

Algorithms & Complexity

Chapter 9 · Beyond Polynomial Time: Exponential Growth & a Taste of P vs. NP

Chapter 1 showed O(2ⁿ) overtaking O(n²) by 32,000× at just n=20. This chapter puts real units on that divergence — actual seconds, days, years — and uses it to introduce the honest, practical boundary between problems that are efficiently solvable and problems nobody has ever found an efficient way to solve.

How Long, Really? Real Wall-Clock Estimates

Assuming a computer doing a generous 1 billion operations per second:

n	O(2ⁿ) operations	Estimated time
20	≈1.05 million	Under a millisecond
30	≈1.07 billion	≈1.1 seconds
50	≈1.13 quadrillion	≈13 days
100	≈1.27 × 10³⁰	≈2,911× the age of the universe

This isn't a hardware problem

A computer a million times faster only pushes that n=100 estimate down to "merely" about 3 million years — still catastrophically longer than any realistic patience. Exponential growth genuinely cannot be out-engineered with faster hardware; only a fundamentally different (polynomial) algorithm changes the picture at all, exactly Chapter 1's own "why choosing a better algorithm matters more than buying speed" point, now with real units attached.

Factorial growth is even more punishing:

n	O(n!) operations	Estimated time
10	≈3.6 million	Under a millisecond
15	≈1.3 trillion	≈22 minutes
20	≈2.4 × 10¹⁸	≈77 years
25	≈1.6 × 10²⁵	≈492 million years

A brute-force approach to something like the traveling salesman problem — checking every possible route ordering, an O(n!) approach — becomes physically hopeless before the input even reaches 25 cities.

A Taste of P vs. NP

Two informal definitions

P — problems solvable in polynomial time. Every algorithm this course has analyzed (searching, sorting, anything O(1) through O(n^k)) is in P.
NP — problems where a proposed solution can be verified in polynomial time, even if nobody knows how to efficiently find one.

Every problem in P is automatically in NP too — if you can solve something quickly, you can obviously check a proposed answer just as quickly (solve it yourself and compare). The genuinely open question, one of the most famous unsolved problems in mathematics and computer science: is P = NP? Is every problem whose solution can be quickly checked also quickly solvable — or are some problems truly, unavoidably harder to solve than to verify? Nobody has ever proven it either way; it's a Millennium Prize Problem with a $1 million reward still unclaimed.

Two accessible NP examples

Sudoku: given a completed grid, checking every row, column, and box is fast — but finding a solution from a mostly-empty puzzle can require real search. Traveling salesman: given a specific route, computing its total distance and checking it's under some target is fast — but finding the genuinely shortest route among n! possible orderings is exactly the factorial blowup shown above.

Certain problems — called NP-complete — are, in a precise sense, the "hardest" problems in NP: if any NP-complete problem were ever found to have a polynomial-time solution, that would prove P = NP and mean every problem in NP could suddenly be solved efficiently too. Traveling salesman is a classic NP-complete problem.

Honest scope note

This is deliberately a light, informal introduction, not a real complexity theory course — proving a problem is NP-complete, formal reductions between problems, and the deep theory behind P vs. NP are genuinely out of scope here, exactly per Chapter 1's own boundary. The goal is awareness of the boundary and roughly what it means, not the machinery to navigate it formally.

The Practical Takeaway

Why this matters for real engineering decisions

If a problem is known (or strongly suspected) to be NP-complete, the practical response isn't to keep hunting for a clever fast exact algorithm — decades of effort by the entire field haven't found one for any NP-complete problem. The real options are: solve it exactly only for genuinely small n (per this chapter's own tables, that means staying well under 20–30 for factorial-shaped problems), use an approximation algorithm that finds a provably good-enough answer quickly, or use a heuristic that works well in practice without any formal guarantee. Recognizing "this looks NP-complete" is itself a useful, actionable signal.

Real Numbers in Code

import math

OPS_PER_SECOND = 1e9

def estimate_seconds(operation_count):
    return operation_count / OPS_PER_SECOND

n = 100
seconds = estimate_seconds(2 ** n)
years = seconds / (365.25 * 24 * 3600)
print(f"{years:.3e} years")  # ~4.02e13 years

n2 = 20
seconds2 = estimate_seconds(math.factorial(n2))
print(f"{seconds2 / (365.25*24*3600):.1f} years")  # ~77.1 years

Hands-On Exercises

Exercise 1

Using this chapter's own 1-billion-operations-per-second assumption, estimate the running time of an O(2ⁿ) algorithm at n = 40. Express the result in a human-readable unit (seconds, minutes, hours, etc.), showing your calculation.

📄 View solution

Exercise 2

Using the same assumption, estimate the running time of an O(n!) algorithm at n = 15, expressed in a human-readable unit. Compare it to this chapter's own O(2ⁿ) estimate at a similar-magnitude operation count, and comment on which grows faster for a given increase in n.

📄 View solution

Exercise 3

Using a Sudoku puzzle as a concrete example, explain in your own words the difference between "solving" a problem and "verifying" a proposed solution to it, and why this distinction is exactly what defines the class NP.

📄 View solution

Chapter 9 Quick Reference

At 1 billion ops/sec, O(2ⁿ) reaches 2,911× the age of the universe by n=100 — no realistic hardware speedup rescues this
O(n!) is even more punishing — 20! alone takes ≈77 years at the same rate
P: solvable in polynomial time. NP: a proposed solution verifiable in polynomial time. Every P problem is in NP; whether the reverse holds (P = NP) is a famous unsolved problem
NP-complete problems are the "hardest" in NP — solving any one in polynomial time would solve all of NP efficiently
Sudoku and the traveling salesman problem are accessible, concrete NP examples — easy to verify, hard (as far as anyone knows) to solve
Practical takeaway: a suspected NP-complete problem calls for approximation or heuristics, not an endless search for a fast exact algorithm
Next chapter: Capstone — analyzing and comparing real algorithms