Compare Growth Against Encoded Input Length

Rank mixed growth rates and distinguish a number from its binary encoding length.

Problem

Let an input contain a positive integer $N$ in binary, so the numeric field has length $n=\lceil\log_2(N+1)\rceil$. Rank

by eventual growth. Then classify each bound as polynomial, superpolynomial, or exponential as a function of the actual input length $n$. Prove every non-obvious comparison rather than relying on names.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

Substitute $N=2^{\Theta(n)}$ only after ranking the functions of $N$.

Hint 2

Take logarithms when comparing positive exponentials.

Hint 3

To compare $2^{\sqrt{\log N}}$ with powers of $N$, write $N^c=2^{c\log N}$.

Full solution

Put $L=\log_2 N$. Taking logarithms where appropriate gives the exponent scales $4\log L$, $\sqrt L$, $L/3$, $L+\log L$, and $N$. Since $\log L=o(\sqrt L)$, $\sqrt L=o(L)$, and $L/3<L+\log L$, the eventual order is

For example,

for every fixed $\varepsilon>0$. Thus the second expression is larger than every fixed polylogarithm in $N$ but smaller than every positive power of $N$.

Now measure against the encoded length. Because $N$ lies between $2^{n-1}$ and $2^n-1$, replacing $N$ by $2^{\Theta(n)}$ preserves the relevant classes. We obtain

which is polynomial in the input length. Next,

This is superpolynomial because for every constant $k$, $\sqrt n-k\log n\to\infty$, so $2^{\sqrt n}/n^k\to\infty$. It is subexponential because $\sqrt n=o(n)$.

The remaining three become

and

The first two are single-exponential in the encoded input length, whereas the last is double-exponential. The polynomial/exponential labels therefore depend on the declared size measure. Calling an $O(N)$ algorithm polynomial is correct only when $N$ symbols are explicitly present; it is generally exponential when $N$ is a binary value.

All conclusions tolerate the ceiling in $n$ and a constant-base change of logarithm. Those changes multiply logarithms or exponents by constants and do not alter eventual domination or the classifications above.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

• Ranking before fixing the size measure.
• Calling $2^{\sqrt n}$ polynomial because its exponent is sublinear.
• Treating $2^N$ as merely single-exponential in $\log N$.

Sources and verification

• Merged summary, pp. 8-13
• 2026 transcript 1
• Sipser 3e, sec. 7.1
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.