Unit 4 · Algorithms & Simulation · Lesson 4.7

Reasonable vs Unreasonable Time

Handshakes grow like n². Seating arrangements grow like n!. One finishes in a day; the other outlasts the universe. Today you compute both and learn the exact line the exam draws between them.

Big Idea 3 — Algorithms & ProgrammingCED 3.17 · precise definition

Before this lesson

No reading — this page is the reading. Runestone doesn’t cover Unit 4 (search, efficiency, limits, simulation), so everything you need is right here.

Where We Are

People→ Bits→ Programs→ Internet→ Security→ Big Data→ Impact

Programs, Algorithms region. 4.6 gave you linear and quadratic. Today the growth rates get steeper — steep enough that the question stops being “how long?” and becomes “will it finish before the sun burns out?”

The Hook

Everyone in this room shakes everyone else’s hand. 32 people: 496 handshakes. A school of 2,000: 1,999,000. Big, but you could do it in a (very long) day.

Now count every possible seating arrangement of the 32 people in this room. The answer has 36 digits — about 2.6 × 10³⁵. Checking one arrangement per nanosecond, you’d still be going long after the universe ends.

The Idea

Handshakes grow like n². Seating arrangements grow like n! (n factorial: n × (n−1) × … × 1). Those are different kinds of growth, and the CED sorts them into two bins:

Growth	n = 10	n = 20	n = 50	Verdict
n	10	20	50	reasonable polynomial
n²	100	400	2,500
n³	1,000	8,000	125,000
2ⁿ	1,024	1,048,576	≈ 1.1 × 10¹⁵	unreasonable exponential, factorial
n!	3,628,800	≈ 2.4 × 10¹⁸	≈ 3.0 × 10⁶⁴	unreasonable exponential, factorial

“Reasonable” has a precise meaning. It means the step count grows like a polynomial — n, n², n³ — or slower. It does not mean “fast enough for me.” A 2ⁿ algorithm is unreasonable even though it finishes instantly at n = 10, and an n³ algorithm is reasonable even when it’s slow on huge inputs. The label is about the shape of the growth.

The traveling salesperson

Visit every city once and return home by the shortest route. The only guaranteed method is to check every route — and the number of distinct round trips through n cities is (n−1)! / 2.

Cities	Distinct routes	At 1 billion routes per second
10	181,440	under a millisecond
20	≈ 6.1 × 10¹⁶	about 2 years
50	≈ 3.0 × 10⁶²	≈ 10⁴⁶ years — the sun has about 5 billion left

Ten cities is fine. Fifty cities outlives the sun. The problem is perfectly solvable — there’s a correct algorithm — it just can’t finish. Hold on to that; it matters on Friday.

Try It — The Growth Grapher

Five growth rates on the same axes. The vertical axis always tops out at n³. Slide n up and watch which curves stay on the screen.

n = 10

Vocabulary

reasonable time Programs: An algorithm whose step count grows like a polynomial (n, n², n³, …) or slower.
unreasonable time Programs: An algorithm whose step count grows exponentially (2ⁿ) or factorially (n!). Solvable in principle; hopeless for large inputs.

Check

Five questions. Judge the growth, not how fast it feels for small n.

0 of 5 answered

Impact Check

Sometimes unreasonable is the point

Your bank’s encryption works because breaking it by brute force means trying every possible key — about 2¹²⁸ of them for a common key size. That’s exponential. Even at a trillion guesses a second, it would take around 10¹⁹ years.

Unreasonable time is a problem when you’re the one trying to solve something — and a shield when you’re the one being protected. You’ll see exactly how in Unit 7.

Connections

Came from 4.6 — linear and quadratic are both polynomial: both reasonable.

Next in 4.8 — if the exact answer takes forever, settle for a good one, fast. That’s a heuristic.

Returns in 4.9 — “takes forever” is NOT the same as “impossible.” The unit’s most-confused pair.

Returns in Unit 7 — encryption is built on problems that take unreasonable time to crack.