How do you decide whether brute-forcing all n! orderings or all 2^n subsets is feasible?
answer
- don't stop at the word exponential
- write the two counts down for n=12
- compare their logarithms, not the words
- one more item: doubles, or multiplies by n?
- divide by 10^8 operations per second
basics
~20 sDo the arithmetic instead of labelling both 'exponential'. At n=12 there are 4,096 subsets but 479 million orderings — a gap of five orders of magnitude. Subsets stay tractable to roughly n=25-30; orderings die around n=12-14.
solid answer
~50 sCompute the actual number and multiply by the work per candidate, rather than stopping at the word "exponential". Seating 12 guests along a banquet table gives 12! ≈ 4.8 × 10^8 orderings; choosing which 12 dishes to serve gives 2^12 = 4,096 subsets. Both are called exponential, but they differ by a factor of ~117,000 at the same n, because log(2^n) = n while log(n!) = Θ(n log n) — factorial growth outruns doubling. Practical thresholds on one machine, at a handful of operations per candidate: n! is viable to about n = 12-14 and hopeless by 20 (20! ≈ 2.4 × 10^18); 2^n is fine to about 25 and painful past 30. And if only k of n items are chosen, the space is C(n, k), which can be dramatically smaller — C(12, 6) is just 924.
go deeper
Know the three counts cold: 2^n subsets, n! orderings, C(n, k) selections. Be able to evaluate them at n = 12 and say which is far larger.
Turn a count into a time estimate: candidates times work per candidate, divided by roughly 10^8 operations per second, and name the n where the approach stops working.
Bring the input cap into it. Argue that an exponential brute force is acceptable when the maximum n is bounded and enforced, and say what guard prevents someone doubling n later.
Own the choice between a simple exponential solution inside a guaranteed input bound and a complex polynomial one the team must maintain, and be explicit about which risk you are accepting.
## The decision this question is really about Before writing an enumeration you should be able to answer, on the back of an envelope, "how many candidates is that, and how long will they take?" The failure mode is not arithmetic error — it is refusing to do the arithmetic at all, because the word "exponential" feels like a verdict. It is not. Plenty of exponential enumerations run in milliseconds at the input sizes that actually occur, and plenty of them are ruled out three inputs later. ## The three state-space sizes worth memorising - **All subsets of n items: 2^n.** Each item is in or out, independently. - **All orderings of n items: n!.** n choices for the first slot, n−1 for the second, and so on. - **All k-sized selections from n: C(n, k).** Peaks in the middle at about 2^n/√n, and is tiny at the extremes. At n = 12: 2^12 = 4,096; 12! = 479,001,600; C(12, 6) = 924. Three numbers spanning six orders of magnitude, from the same n. This is the single most useful fact in the leaf, because "exponential" collapses all three into one undifferentiated blob. ## Why factorial is in a different class Compare the logarithms. log2(2^n) = n — a straight line. log2(n!) = Θ(n log n) — a line that curves upward. So n! is not merely a bigger exponential; it grows faster than any fixed base raised to n. Concretely, going from n to n+1 doubles a subset space but multiplies an ordering space by n+1. At n = 20, one more guest costs you 21× the work; one more dish costs you 2×. | n | 2^n | n! | |---|---|---| | 10 | 1.0 × 10^3 | 3.6 × 10^6 | | 12 | 4.1 × 10^3 | 4.8 × 10^8 | | 15 | 3.3 × 10^4 | 1.3 × 10^12 | | 20 | 1.0 × 10^6 | 2.4 × 10^18 | | 30 | 1.1 × 10^9 | 2.7 × 10^32 | ## Turning counts into time A rough, defensible calibration: one core does on the order of 10^8 to 10^9 simple operations per second. Divide the candidate count by that and multiply by the work each candidate costs. Seating 12 guests, scoring each arrangement by summing 11 adjacent-pair rapport values — about 11 operations per candidate — gives 4.8 × 10^8 × 11 ≈ 5 × 10^9 operations: seconds to a minute. Entirely reasonable to run once, overnight or not. Add three guests and 15! × 14 ≈ 1.8 × 10^13 lands in the many-hours-to-days range. Add three more and 18! is 6.4 × 10^15 — done. The cliff between "trivially fine" and "physically impossible" spans about six values of n, which is exactly why the estimate has to be done in advance rather than discovered by watching a progress bar. The headline thresholds worth carrying, at light per-candidate work on one machine: - n! — comfortable to about 11, borderline 12-14, gone by 16. - 2^n — comfortable to about 22, borderline 25-30, gone by 40. - C(n, k) with small k — often fine for n in the hundreds; C(100, 3) is only 161,700. ## Three corrections people get wrong **"Exponential means impossible."** No. It means the viable input range is small and hard-capped. If the product manager can promise n ≤ 10, an exponential enumeration is a perfectly good engineering answer — simple, obviously correct, no clever invariant to maintain. The right question is not "is it exponential" but "what is the largest n we will ever be handed, and what happens the day someone hands us n+5". **"Both are exponential, so they're equally bad."** The table above is the refutation. Reformulating a problem from "try every ordering" to "try every subset" is a genuine, order-of-magnitude win even though both remain exponential — and it is a very common reformulation, because the order often doesn't affect the answer once the set is fixed. **"Big-O settles it."** Big-O hides constants and per-candidate work, and both matter enormously here. An enumeration of 4,096 subsets that does an expensive scoring pass per subset can easily be slower than 479 million trivially-scored orderings. Multiply the count by the per-candidate cost before you conclude anything. ## What to say out loud "That's n!, so about 5 × 10^8 arrangements at n = 12 — a few seconds with cheap scoring, so yes, we can brute force it today. But it multiplies by n each time the guest list grows, so n = 16 is already out; if the list can reach twenty we need a different formulation, not a faster loop." That answer demonstrates the estimate, the threshold and the fragility, which is all the question is after.
- Someone says both 2^n and n! are exponential, so the distinction doesn't matter. What do you tell them?That log(2^n) is n while log(n!) is Theta(n log n), so factorial outgrows every fixed base raised to n. At the same n = 12 they differ by a factor of about 117,000, and each added item doubles one while multiplying the other by n. Reformulating from orderings to subsets is a real win even though both stay exponential — it is often the difference between a job that finishes and one that doesn't.
- You measure the enumeration at n = 10 and it finishes instantly. Why is that a weak basis for shipping?Because exponential curves are flat until they aren't. An n! enumeration at 10 is 3.6 million candidates; at 15 it is 1.3 trillion, roughly 360,000 times more. A benchmark at the small end tells you nothing about the largest input production will hand you, so the guard has to be an explicit cap on n plus an estimate at that cap, not an observed runtime.
- When is choosing k of n items much cheaper than trying all subsets?Whenever k is far from n/2. C(n, k) peaks in the middle at roughly 2^n over the square root of n, but falls off sharply toward the ends: C(100, 3) is 161,700 while 2^100 is astronomically large. So a constraint like 'exactly three of these' turns an impossible subset scan into a trivially small one, and recognising that the constraint shrinks the state space is often the whole optimisation.
Subsets ask each item a yes/no question; orderings ask you to rank everyone. Adding one person adds one coin flip to the first and a whole extra shuffle to the second.
saying these in an interview costs you the question
- Treats 2^n and n! as interchangeably hopeless
- Calls exponential automatically unshippable without checking n
- Estimates the count but ignores per-candidate work
- Benchmarks at small n and extrapolates linearly
- Thinks n! is just 2^n with a bigger constant