P — polynomial time: Worked examples — Coding deep dive

The scenario matrix

Here is every kind of situation a "is it in P?" question can throw at you. Each column is a trap or a case you must be able to handle. The worked examples below are labelled with the cell they hit.

Cell	Case class	The question it tests	Covered by
C1	Clean poly (small exponent)	Count steps, get $O (n^{2})$ -ish, done	Ex 1
C2	"Value vs length" trap	Time looks small but is exponential in bits	Ex 2
C3	Ugly-but-still-poly ( $n^{100}$ )	Big exponent — still in P?	Ex 3
C4	Nested/composed subroutines	poly-inside-poly stays poly	Ex 4
C5	Degenerate / zero / empty input	$n = 0$ , empty graph, single vertex	Ex 5
C6	Limiting behaviour ( $n \to \infty$ )	Which term wins? does it stay poly forever?	Ex 6
C7	Real-world word problem	Translate a story into a step-count	Ex 7
C8	Exam twist: "reduces to X"	Poly reduction preserves P-membership	Ex 8
C9	The fake-poly exponential	$2^{n}$ , $n^{l o g n}$ — poly or not?	Ex 9

We now walk all nine.

Worked example Example 1 — Sorting a list (Cell C1: clean poly)

Statement: You are given a list of $n$ numbers. Question: "Can this list be arranged in non-decreasing order?" (trivially yes, but treat it as sort it and check). Is the sorting work polynomial in the input size?

Forecast: Guess the growth of insertion sort before reading on — is it $n$ , $n^{2}$ , or $2^{n}$ ?

Count the comparisons. Insertion sort, to place element $i$ , compares it against up to $i - 1$ earlier elements. Total comparisons $\leq 0 + 1 + 2 + \dots + (n - 1) = \frac{n ( n - 1 )}{2}$ . Why this step? We prove membership by counting elementary operations, not by feeling.
Bound by a polynomial. $\frac{n ( n - 1 )}{2} = \frac{n ^{2} - n}{2} \leq n^{2}$ for all $n \geq 1$ . Why this step? A term-by-term upper bound turns an exact count into a clean $O (n^{2})$ polynomial.
Conclude. $n^{2}$ is a polynomial in the input length $n$ (the list has $n$ items). ✅ Sorting is in P.

Verify: at $n = 5$ , comparisons $\leq \frac{5 \cdot 4}{2} = 10$ , and $10 \leq 5^{2} = 25$ . ✓ Bound holds.

This is the template: count → bound → declare polynomial. Every other example bends this template.

Worked example Example 2 — "Is

$N$ divisible by any number below $N$ ?" (Cell C2: value-vs-length trap) Statement: Given an integer $N$ written in binary, trial-divide it by every integer from $2$ up to $⌊ N ⌋$ . Does this prove the problem is in P?

Forecast: $N$ "feels small." Guess yes/no before reading.

Identify the true input size. $N$ in binary uses $n = ⌈ lo g_{2} N ⌉$ bits. So $N \approx 2^{n}$ . Why this step? Complexity is always measured against the encoding length, never the numeric value — this is the "bits, not value" rule.
Rewrite the step-count in terms of $n$ . Number of divisions $\approx N = 2^{n} = 2^{n /2}$ . Why this step? We must express the work in the same variable ( $n$ ) that defines input size, or the comparison is meaningless.
Classify. $2^{n /2}$ is exponential in $n$ , not polynomial. Why this step? No polynomial $c n^{k}$ eventually dominates $2^{n /2}$ (see Ex 6).
Conclude. Trial division is NOT a P-proof. ❌ (PRIMES is in P — but only via AKS, polynomial in $n = lo g N$ , see the parent note.)

Verify: For a 60-bit number $N \approx 2^{60}$ , trial division does $\approx 2^{30} \approx 1.07 \times 1 0^{9}$ divisions. If it were poly like $n^{3}$ we'd expect $6 0^{3} = 216, 000$ . The gap ( $1 0^{9}$ vs $2 \times 1 0^{5}$ ) is the exponential blow-up laid bare. ✓

Look at the figure: the teal polynomial curve $n^{3}$ is visibly crushed by the orange $2^{n /2}$ once $n$ passes the crossover. That crossover is exactly why "value looks small" lies to you.

Worked example Example 3 — Does

$n^{100}$ live in P? (Cell C3: ugly-but-still-poly) Statement: An algorithm runs in exactly $n^{100}$ steps. Is the problem it solves in P?

Forecast: $n^{100}$ is astronomically slow in practice. Poly or not?

Check the definition, not your feelings. P requires some constants $c, k$ with runtime $\leq c n^{k}$ . Take $c = 1$ , $k = 100$ . Why this step? Membership in P is a definitional yes/no, decoupled from real-world speed (Mistake B in the parent).
Match. $n^{100} \leq 1 \cdot n^{100}$ . Satisfied. Why this step? The exponent $100$ is a fixed constant — it does not grow with $n$ — so $n^{100}$ is a genuine polynomial.
Conclude. ✅ Yes, it is in P — even though nobody would run it.

Verify: "polynomial" means the exponent is a constant. $100$ is constant; $lo g n$ or $n$ as an exponent would NOT be (contrast Ex 9). ✓ At $n = 2$ , $n^{100} = 2^{100}$ : huge — but still a fixed power of $n$ , so still poly.

The lesson: P is a boundary of principle, not a promise of speed.

Worked example Example 4 — A loop calling a subroutine (Cell C4: composition)

Statement: Algorithm $B$ runs a loop $n^{2}$ times, and inside each iteration calls subroutine $A$ that itself costs $n^{3}$ steps. Total time class?

Forecast: Multiply or add the exponents? Guess the total.

Multiply work per call by number of calls. Total $= (iterations) \times (cost per call) = n^{2} \cdot n^{3}$ . Why this step? Nested repetition multiplies: the same expensive block runs once per loop pass.
Combine exponents. $n^{2} \cdot n^{3} = n^{2 + 3} = n^{5}$ . Why this step? Laws of exponents: multiplying powers of the same base adds exponents.
Conclude. $n^{5}$ is polynomial. ✅ This is the composition property: poly inside poly is poly. If instead $A$ called another poly routine, we'd add another constant to the exponent — still finite, still poly.

Verify: at $n = 10$ : $1 0^{2} \cdot 1 0^{3} = 100 \cdot 1000 = 100, 000 = 1 0^{5}$ . ✓ Matches $n^{5}$ .

This is the reason polynomials were chosen as the feasibility line — the family survives being stacked on itself.

Worked example Example 5 — Degenerate inputs (Cell C5: zero / empty / single)

Statement: Run BFS-reachability on three edge cases: (a) empty graph ( $0$ vertices), (b) one vertex, no edges, asking "is $s$ reachable from $s$ ?", (c) two vertices, no edge, asking "is $t$ reachable from $s$ ?" Does the $O (V + E)$ bound still hold?

Forecast: Do tiny/empty inputs break the polynomial bound?

Case (a), empty graph. $V = 0, E = 0$ . Work $= O (0 + 0) = O (0)$ — the algorithm does a constant amount of setup and halts. Bound $c n^{k}$ with $n = 0$ still $\geq$ constant setup if we set $c$ to cover the constant term. Why this step? Polynomial bounds must include a constant so the $n = 0$ / small- $n$ cases don't violate them — we always write $c n^{k} + c^{'}$ implicitly.
Case (b), self-reachability. $s$ is trivially reachable from itself: answer yes in $1$ step. $V = 1, E = 0$ , work $O (1)$ . ✅ Poly (constant is a degree-0 polynomial). Why this step? Degenerate "yes by definition" inputs still cost a bounded amount — they cannot escape P.
Case (c), disconnected. BFS from $s$ visits only $s$ , never reaches $t$ : answer no. Work $O (V + E) = O (2 + 0)$ . ✅ Why this step? The "no" branch is just as bounded as "yes"; both outcomes must halt in poly time for the decision problem to be in P.

Verify: For (c), $V + E = 2 + 0 = 2$ , and $n^{2} = 2^{2} = 4 \geq 2$ . ✓ Bound survives the smallest non-trivial graph. Constant-time halting = degree-0 polynomial ✓.

Takeaway: always poke $n = 0$ and $n = 1$ . A class definition that broke on empty input would be worthless — P doesn't.

Worked example Example 6 — The limit that decides everything (Cell C6: limiting behaviour)

Statement: Does any fixed polynomial $c n^{k}$ eventually overtake $2^{n /2}$ ? This is the mathematical heart of why Ex 2's trap is fatal.

Forecast: Can a big-enough exponent $k$ let $n^{k}$ stay above $2^{n /2}$ forever?

Form the ratio and take the limit. Consider $n \to \infty lim \frac{n ^{k}}{2 ^{n /2}}$ . Why this step? Taking a limit is the right tool because "who wins for all large $n$ " is precisely a statement about asymptotic dominance — a limit answers "which grows faster forever?"
Evaluate. Exponentials beat every fixed polynomial: the limit is $0$ for every constant $k$ . Why this step? No matter how large $k$ is, doubling ( $2^{n /2}$ ) compounds; a fixed power cannot keep pace. This is why "polynomial" and "exponential" are cleanly separated classes.
Conclude. $2^{n /2}$ is not $O (n^{k})$ for any $k$ . So trial division can never be repackaged as polynomial. ✅ (consistent with Ex 2).

Verify: at $n = 100$ , $k = 3$ : $\frac{n ^{k}}{2 ^{n /2}} = \frac{1 0 ^{6}}{2 ^{50}} \approx \frac{1 0 ^{6}}{1.13 \times 1 0 ^{15}} \approx 8.9 \times 1 0^{- 10}$ — already vanishingly small. The trend to $0$ is unmistakable. ✓

Worked example Example 7 — Word problem: delivery route feasibility (Cell C7: real-world)

Statement: A courier has a road network of $V$ towns and $E$ roads. Question: "Starting at the depot $s$ , can the courier reach delivery point $t$ at all (ignoring cost)?" Model it and show it's in P.

Forecast: Is reachability the hard travelling-salesman monster, or the easy BFS one?

Strip the story to a decision problem. "Can $s$ reach $t$ ?" = graph reachability. There is no ordering/minimisation asked — just yes/no connectivity. Why this step? The real trap in word problems is smuggling in optimisation. Reading carefully, we asked only reachability, which is the easy cousin.
Pick the algorithm and count. BFS from $s$ : $O (V + E)$ steps (each town enqueued once, each road scanned twice). Why this step? We reuse the proven bound; input size $n = V + E$ (the size of the map description).
Bound and conclude. $V + E \leq n^{2}$ , polynomial. ✅ Route feasibility is in P. Why this step? Contrast: asking for the shortest route visiting all towns would be the NP-hard travelling-salesman decision problem — a different beast entirely. Reading the exact question matters.

Verify: A 5-town map with 6 roads: work $\leq V + E = 11$ ; $n^{2} = 1 1^{2} = 121 \geq 11$ . ✓ Feasibility stays firmly in P.

Worked example Example 8 — Exam twist: "problem A reduces to B in poly time, B ∈ P" (Cell C8: reduction preserves P)

Statement: You're told $A$ reduces to $B$ via a polynomial-time transformation, and $B \in P$ . Prove $A \in P$ .

Forecast: Does chaining "poly reduction" + "poly decider" stay poly?

Name the two poly stages. The reduction turns input $x$ (size $n$ ) into input $y$ for $B$ in time $\leq c_{1} n^{a}$ ; crucially $y$ has size $\leq c_{1} n^{a}$ too (you can't write more output than time spent). Why this step? Bounding the size of $y$ is essential — the next stage's cost depends on it.
Run $B$ 's decider on $y$ . Cost $\leq c_{2} ∣ y ∣^{b} \leq c_{2} (c_{1} n^{a})^{b} = c_{2} c_{1}^{b} n^{ab}$ . Why this step? We substitute the bound on $∣ y ∣$ into $B$ 's polynomial runtime — composing the two polynomials.
Total. $c_{1} n^{a} + c_{2} c_{1}^{b} n^{ab} \leq C n^{ab}$ for large $n$ . Polynomial. ✅ So $A \in P$ . Why this step? Sum of two polynomials is a polynomial; this is exactly why P is closed under poly-time reductions.

Verify: with $a = 2$ , $b = 3$ : dominant term $n^{ab} = n^{6}$ . At $n = 10$ : reduction $\leq 1 0^{2} = 100$ , decider $\leq (100)^{3} = 1 0^{6}$ ; total $\approx 1 0^{6} = 1 0^{6}$ , matching $n^{6}$ . ✓

Worked example Example 9 — The impostors:

$2^{n}$ and $n^{l o g n}$ (Cell C9: fake-poly) Statement: Two runtimes look "in between." Classify each: is it polynomial (⟹ in P) or not?

Forecast: $2^{n}$ grows slowly; $n^{l o g n}$ has a variable exponent. Poly or not — guess both.

Test $2^{n}$ against the definition. Is there a constant $k$ with $2^{n} \leq n^{k}$ ? Take logs (base 2): $n \leq k lo g_{2} n$ ? As $n \to \infty$ , $n$ crushes $lo g_{2} n$ . No such $k$ . Why this step? Taking logarithms turns "polynomial vs not" into a comparison of exponents — $n$ vs $lo g n$ — where $n$ clearly wins. So $2^{n}$ is super-polynomial. ❌ Not a P-proof.
Test $n^{l o g n}$ . Its exponent is $lo g n$ , which grows with $n$ . A polynomial needs a constant exponent. Why this step? $n^{l o g n} = 2^{(l o g n)^{2}}$ — the exponent $(lo g n)^{2} \to \infty$ , so it beats every fixed $n^{k}$ . ❌ Not polynomial either ("quasi-polynomial").
Conclude. Both are strictly between poly and $2^{n}$ , but neither is in P by these runtimes.

Verify: at $n = 256$ : $n = 16$ , so $2^{n} = 2^{16} = 65536$ , while $n^{2} = 65536$ too — they tie here — but at $n = 1024$ : $2^{n} = 2^{32} \approx 4.3 \times 1 0^{9}$ vs $n^{2} \approx 1.05 \times 1 0^{6}$ . The impostor pulls ahead → super-poly confirmed. ✓

The figure ranks all the growth families we met — poly (teal), the impostors (plum), the true exponential (orange) — so you can see the impostors sit above every polynomial forever.

The matrix, filled in

Active Recall

Recall Test yourself before moving on

Why does trial division fail as a P-proof? ::: Its step-count $N = 2^{n /2}$ is exponential in the bit-length $n = lo g_{2} N$ (Ex 2, Ex 6). A loop of $n^{2}$ calls a subroutine costing $n^{3}$ — total class? ::: $n^{5}$ , polynomial; nested repetition multiplies, exponents add (Ex 4). Is $n^{100}$ in P? ::: Yes — the exponent is a fixed constant, so it is a genuine polynomial (Ex 3). Is $n^{l o g n}$ in P by that runtime? ::: No — the exponent grows with $n$ , so it is super-polynomial (Ex 9). Does the $O (V + E)$ bound survive an empty graph? ::: Yes — constant setup is a degree-0 polynomial; both yes and no branches halt in bounded time (Ex 5).

Connections

Parent: P — polynomial time
Time complexity & Big-O
Polynomial-time reductions
NP-complete problems
TIME complexity classes
Cobham–Edmonds thesis