skip to content

Two proposed maintenance rules give valid-schedule counts growing like 1.62^n and 2^n — what should that difference change about the design?

level: principalimportance: should knowfreq 28%

answer

  1. compare exponents, not one value
  2. both exponential, neither enumerable
  3. a smaller base buys reach, not class
  4. watch the counter's width
  5. feasibility fact, not a preference

basics

~20 s

Less than it first appears. Both counts are exponential, so neither space can be enumerated at realistic n; the tighter rule buys a growing factor — roughly 4,000 times fewer schedules at n=40 — which helps pruning and reach, not feasibility in kind.

solid answer

~40 s

Read the exponent, not one value. Both rules give exponential configuration spaces, so any plan that materialises every valid schedule dies under either — the smaller base delays the wall rather than removing it. What the difference genuinely buys is **reach**: for a fixed budget of ten million configurations you can walk about 33 slots under the `1.62^n` rule against about 23 under `2^n`, because reachable `n` scales as the inverse of the log of the base. It also matters for arithmetic: `2^n` passes a signed 64-bit range at `n = 63`, the slower count at around `n = 91`, so a naive counter silently wraps and turns a capacity claim negative. The rule itself should still be chosen for what it protects operationally; the count decides which implementation plans survive.

go deeper

for a junior

Take away that both counts grow exponentially with the number of slots, so listing every valid schedule stops being possible well before the window gets large.

for a middle

Be able to convert a growth base into a reachable size: the walkable n is the log of the budget divided by the log of the base, which is why 1.62 reaches further than 2.

for a senior

Demonstrate the operational reads — where a fixed-width counter wraps, where a pruned search leaves budget, and why the exact count is still iterated rather than taken from an irrational closed form.

for a principal

Keep feasibility and policy apart. Choose the validity rule for what it protects, then use its growth base to rule out enumeration-based designs and to name the size at which the system must reason instead of list.

## What the two numbers actually say Two candidate validity rules for a maintenance window of `n` slots produce two different counts of valid schedules. One grows like `1.62^n` — the no-two-adjacent rule, whose exact count comes from a second-order recurrence with dominant characteristic root about 1.618. The other grows like `2^n` — every slot free. Both are exponential in `n`. The base differs, and the whole judgment turns on what a base difference does and does not buy. ## What the difference genuinely decides 1. **Reach for an exhaustive walk.** For a budget of `X` configurations, the largest walkable `n` is about `log(X)/log(base)`. At ten million configurations that is roughly 33 slots for the slower growth and roughly 23 for the faster — about 44 percent more slots for the same effort. Real, useful, and finite. 2. **Headroom for a pruned search.** A smaller base means each additional slot multiplies the frontier by less, so a search with good pruning stays inside budget for longer. This is where the tighter rule pays off in practice. 3. **Arithmetic width.** The counts themselves overflow. `2^n` passes the range of a signed 64-bit two's-complement integer at `n = 63`; the slower count reaches it around `n = 91`. A wrapped counter reports a negative capacity, which is a far worse failure than a slow one. | question | count ~1.62^n | count 2^n | |---|---|---| | slots walkable within 10 million configurations | about 33 | about 23 | | configurations at n = 40 | about 2.7 x 10^8 | about 1.1 x 10^12 | | n at which the count leaves a signed 64-bit range | about 91 | 63 | At `n = 40` the tighter rule leaves roughly four thousand times fewer schedules. That factor itself grows with `n`, which is exactly why quoting a ratio at a single `n` is a mistake — it is not a constant discount. ## What the difference does not decide - **It does not make either space enumerable.** A plan to precompute and cache every valid schedule fails under both rules at any `n` a real window would use. - **It does not choose the rule.** The rule exists to protect something operationally; the count says which implementations of it are viable, not which policy is right. - **It does not change the complexity class.** Both are exponential. Presenting `1.62^n` as tractable because the base is under two is the most common way this analysis is mis-sold to a review. - **It is not fixed by hardware.** An extra order of magnitude of compute buys a handful of extra slots — about 13 more under the slower growth, about 10 under the faster — and then the wall returns. ## Where the exact count still earns its keep The asymptotic answers feasibility; the exact number answers the operational question. It is worth computing exactly, by iterating the recurrence rather than evaluating an irrational-root closed form, because: - it validates the recurrence against brute force at small `n`, which is the only real defence against an off-by-one in the base cases; - it bounds the worst case of a pruned search, which is what an on-call owner actually wants to know; - it lets a capacity statement name the exact `n` at which a strategy stops working, instead of gesturing at exponential growth. ## The judgment, stated plainly The exponent is a **feasibility fact**, not a design preference. A lead's job here is to keep the two apart: choose the validity rule on operational grounds, then use its growth base to kill any plan that assumes the configuration space can be walked, and to set the `n` beyond which the system must reason about schedules rather than list them. A genuine change of kind requires a rule whose count is polynomial — for example, capping the total number of maintenance slots at a fixed `k`, which leaves on the order of `n^k` schedules — and that is a policy change, not an optimisation.

  • At what n does each count stop fitting in a signed 64-bit integer, and why care?
    `2^n` leaves the range at `n = 63`, the `1.62^n` count at around `n = 91`. A fixed-width counter wraps silently under two's-complement arithmetic, so the capacity report turns negative rather than failing loudly — either cap the reported value or accumulate at arbitrary precision.
  • If both counts are exponential, why compute them exactly at all?
    Because feasibility and operations are different questions. The exponent says whether enumeration can ever work; the exact value says whether tonight's window of 28 slots is walkable, bounds a pruned search's worst case, and validates the recurrence against brute force at small sizes.
  • What kind of rule change would actually change the class rather than the base?
    One that makes the count polynomial. Capping the total number of maintenance slots at a fixed `k` leaves on the order of `n^k` schedules, which is enumerable for real `n`. That is a policy decision about what the window is allowed to contain, not a tuning of the existing rule.

saying these in an interview costs you the question

  • Calls the 1.62^n rule tractable because its base is below two
  • Compares the two counts at one small n and generalises the ratio
  • Plans to precompute and cache every valid schedule
  • Assumes more hardware makes the smaller space exhaustively searchable
  • Treats the constant in front of the exponential as the deciding factor