A job enumerates every subset of n rooms with O(n) work each — why is n = 18 fine but n = 25 not?
answer
- Count the subsets, then the work inside each
- Every extra element doubles the count
- 2^18 is about a quarter million
- Multiply that by the inner loop's n
- 2^25 times 25 is near 10^9
basics
~20 sBecause the cost is 2^n times n, not 2^n alone. At n = 18 that is about 4.7 million operations; at n = 25 it is roughly 840 million — nearly an order of magnitude past a one-second budget.
solid answer
~40 sEvery extra element doubles the number of subsets, so the count runs 2^18 ≈ 262,000 against 2^25 ≈ 33.5 million — already 128x. Then multiply by the work done inside each subset: with an O(n) inner pass that is about 4.7 × 10^6 at n = 18 versus 8.4 × 10^8 at n = 25, and only the first fits the rough 10^8-operations-per-second budget. The practical ceiling therefore depends on the polynomial factor: bare `2^n` survives to about n = 25, `2^n · n` to about n = 20–22, and `2^n · n^2` only to about n = 17. That is also why a suspiciously tiny bound like "at most 18 rooms" is itself the signal — no one caps an input at 18 unless the intended solution is exponential in it.
code
pseudocode · 9 linesfeasible = 0
for subset in 0..2^n - 1: // 2^n iterations
total = 0
for i in 0..n-1: // n work per subset
if i is a member of subset:
total = total + seats[i]
if total >= demand:
feasible = feasible + 1
...go deeper
Recall that a bound around twenty is the signal that trying every subset is allowed, and that each extra element doubles the number of subsets. Be able to say 2^20 is about a million.
Do the multiplication out loud: subset count times work per subset. Explain why the practical ceiling differs between 2^n, 2^n times n, and 2^n times n squared.
Show that you split a constraint block with two bounds into two budgets, and that you know an exponential path must sit behind an enforced cap because its cost cliff is only a few elements wide.
Own the question of whether a tiny cap is a durable product invariant. If the count can grow, decide up front whether you accept the cliff, enforce the limit, or pay for an approximate approach instead.
## Two multiplications, not one The mistake this question aims at is quoting the subset count and stopping there. The running time of a subset sweep is **the number of subsets times the work done inside each one**, and the second factor is usually the thing that decides whether a bound is comfortable or hopeless. Start with the count. A set of n elements has 2^n subsets, so each additional element *doubles* the search: - 2^18 ≈ 2.6 × 10^5 - 2^20 ≈ 1.0 × 10^6 - 2^25 ≈ 3.4 × 10^7 - 2^30 ≈ 1.1 × 10^9 On its own, 2^25 is fine — thirty-four million steps sits inside a one-second budget. It is the inner work that kills n = 25. Scoring a subset by scanning its members costs O(n), so the total is 2^n · n: - n = 18: 2.6 × 10^5 × 18 ≈ 4.7 × 10^6 — comfortable - n = 22: 4.2 × 10^6 × 22 ≈ 9.2 × 10^7 — borderline - n = 25: 3.4 × 10^7 × 25 ≈ 8.4 × 10^8 — roughly eight times over budget So there is no single "exponential ceiling". There is a ceiling per polynomial factor: | Total cost | Practical ceiling on n | | --- | --- | | 2^n | ~25–27 | | 2^n · n | ~20–22 | | 2^n · n^2 | ~16–18 | | n! | ~11–12 | ## Reading the bound backwards The more useful direction is the reverse one. Constraints in the 15–25 range are rare and deliberate. Nothing about rooms, flags, or optional features naturally stops at 18; a bound that small is the author telling you the intended solution is exponential in that quantity, because if a polynomial solution existed the bound would have been 10^5. That inference has real interview value. Faced with "at most 18 optional rooms and up to a million bookings", you should immediately split the problem along its two bounds: exponential in the 18, at most linear or linearithmic in the million. The bounds are not one budget — they are a shape. ## Where the doubling bites The practical consequence of doubling is how *narrow* the safe zone is. Going from n = 20 to n = 25 is a factor of 32; from 25 to 30 another factor of 32. An algorithm that runs in 50 ms at n = 20 runs about 1.6 s at n = 25 and about 50 s at n = 30, all with identical code. This is why an exponential solution must be paired with a hard, enforced bound rather than a hopeful one: there is no graceful degradation, only a cliff two or three elements wide. It is also why constant-factor work matters more here than almost anywhere else. Shaving the inner pass from O(n) to O(1) — by carrying a running total from a previously computed subset instead of rescanning — buys back a factor of n, which is worth roughly four extra elements of headroom at these sizes. Trimming branches that cannot lead to an answer buys more, though it changes the worst case not at all: the bound stays 2^n and only the typical run improves. ## The direction of the claim Two precision points worth stating out loud: 1. **2^n is a worst-case upper bound.** A sweep that prunes aggressively may visit a tiny fraction of the subsets on real input while still being labelled exponential. The label rules the approach *in* for a bound of 18; it does not promise the machine will execute 262,144 iterations. 2. **Exponential is about the exponent's base quantity.** "Exponential" said of a problem with two size parameters is meaningless until you say exponential *in which one*. A cost of 2^r · b, with r rooms and b bookings, is perfectly practical when r is capped at 18 and b is a million — and calling it "exponential, therefore infeasible" would be a straightforward misread of the constraints. ## What to say in an interview Name the two factors separately: "There are 2^18 subsets, about 260,000, and I do about 18 units of work in each, so roughly five million operations — fine. At 25 that is 840 million, which is not." Doing the multiplication out loud is the whole answer, and it is what separates a candidate who recognises the cue from one who has memorised the phrase "n ≤ 20 means exponential".
- How would you buy back headroom without changing the approach?Kill the inner pass. If each subset is generated from one already scored by adding a single element, carry the running total forward instead of rescanning members — that turns 2^n · n into 2^n and buys roughly four more elements of room. Pruning branches that cannot beat the current best helps typical inputs further, but leaves the worst case at 2^n.
- A constraint block says at most 18 rooms and up to a million bookings — what shape does that imply?Two bounds mean two budgets. The tiny one licenses exponential work in the rooms; the large one demands at most linear or linearithmic work in the bookings. So the design is a sweep over 2^18 room subsets with a cheap, precomputed check per subset — never a scan of a million bookings inside the exponential loop, which would be 2.6 × 10^11 operations.
- Is a solution labelled O(2^n) always infeasible?No — the label is an upper bound on the worst case. With a hard cap of 18 it is entirely practical, and with heavy pruning a sweep may visit a small fraction of the subsets on real input. What the label does tell you is that there is no graceful degradation: the cost multiplies by about 32 for every five elements past the cap.
It is like pricing a trip by the number of stops and forgetting the cost at each stop: seven stops at a dollar and seven stops at a hundred are the same itinerary and a very different bill.
saying these in an interview costs you the question
- Quotes the subset count and ignores the work per subset
- Claims one fixed ceiling for all exponential algorithms
- Calls anything exponential infeasible regardless of the bound
- Says exponential without naming which quantity it is exponential in
- Expects an exponential solution to degrade gracefully past its cap