Why does bitmask DP over subsets stay feasible near n = 20 but collapse by n = 30?
answer
- each extra element doubles something
- ten more elements is a factor of 1024
- count table entries before counting time
- 2^30 times 30 is about 3 × 10^10
- memory runs out before the clock does
basics
~10 sEach extra element doubles the table. Over 20 elements a dp[mask][last] table holds about 21 million entries; over 30 it holds roughly 32 billion — far past memory before a single transition is counted.
solid answer
~40 sGrowth is multiplicative in the number of elements, not in the input size you are used to: ten more elements is a factor of 1024. Concretely, a `dp[mask][last]` table has 2^n·n entries — about 2.1 × 10^7 at n = 20, about 3.2 × 10^10 at n = 30. At four bytes an entry that is roughly 84 MB versus 128 GB, so **memory fails before time does**. Transition counts tell the same story: 2^n·n^2 is around 4 × 10^8 at n = 20 and around 10^12 at n = 30. That is why a problem statement capping n at 18 or 20 while asking for an optimum over subsets or orderings is a flashing sign for subset DP — the bound exists precisely because the intended solution is exponential in n.
go deeper
Know that a subset-indexed table has 2^n entries and that this doubles with every added element, so the technique lives in the range of roughly fifteen to twenty items, not hundreds.
Be able to compute the numbers on the spot — states, transitions and bytes — and say which one runs out first. Interviewers use this to check that you reason about feasibility before you start designing.
Show you can read a size bound as a design signal, and be honest about what tuning buys: narrower entries and layering are constant factors, not a new ceiling.
Frame the wall as a requirements conversation: if the business needs more elements than the exact method admits, the decision is about acceptable optimality gap and maintenance cost, not about optimising the current table.
## The arithmetic, first A DP whose state is a subset has 2^n states before any other dimension. Add an endpoint or a position index and it is 2^n·n. Iterate the possible next choices inside each state and the transition count is 2^n·n^2. Those three numbers are the whole feasibility argument: | n | masks 2^n | states 2^n·n | transitions 2^n·n^2 | table at 4 bytes/entry | |---|---|---|---|---| | 15 | 3.3 × 10^4 | 4.9 × 10^5 | 7.4 × 10^6 | ~2 MB | | 18 | 2.6 × 10^5 | 4.7 × 10^6 | 8.5 × 10^7 | ~19 MB | | 20 | 1.0 × 10^6 | 2.1 × 10^7 | 4.2 × 10^8 | ~84 MB | | 25 | 3.4 × 10^7 | 8.4 × 10^8 | 2.1 × 10^10 | ~3.4 GB | | 30 | 1.1 × 10^9 | 3.2 × 10^10 | 9.7 × 10^11 | ~128 GB | Read down the last column rather than the transition column, because that is the one that stops you first. At n = 25 you are already asking for gigabytes of table for a single planning call; at n = 30 no machine you were given holds it. ## Why intuition misleads here Engineers are trained on polynomial growth, where doubling the input costs a predictable 2×, 4× or 8×. Exponential growth is per *element*: every new item multiplies the whole table by two. Going from 20 to 30 elements is not "1.5× the work", it is 2^10 = 1024× the states and about 2300× the transitions once the n^2 factor moves too. This is why the common wrong answer — "2^n is fine up to about 30" — is off by three to four orders of magnitude in practice. Around 2^30 you are looking at 3 × 10^10 states; even at one byte per state and a nanosecond per state that is half a minute of pure memory traffic, and nothing real runs at one state per nanosecond. ## Where the practical ceiling actually sits About **n ≤ 20–22** for the full `dp[mask][last]` form with O(n) transitions, and a little higher — maybe 24–25 — when the state is just `dp[mask]` with cheap transitions and you are willing to spend gigabytes. Below n = 18 it is comfortable enough that you can be careless. Above 22 you need either a different algorithm class or a way to shrink n itself (merge items, decompose the instance, prune unreachable masks). ## Reading the ceiling backwards The ceiling is also a *hint mechanism*. When a statement bounds n at 15, 18 or 20 while asking for an exact optimum over which elements are chosen or in what order they are visited, that bound is doing real work: it is small enough that 2^n is affordable and far too small to be a meaningful limit for any polynomial method. A polynomial solution would happily take n in the thousands, so the author would not have bothered capping it at 18. Treat the pairing of *tiny n* with *exact combinatorial objective* as the signature, not the tiny n on its own. ## Buying a little headroom Several things buy constant factors, and it is worth knowing that they are only constant factors: - **Narrower entries.** Storing costs in two bytes instead of eight is a 4× saving — one extra element's worth. - **Layering by the number of chosen elements.** If every transition adds exactly one element, only two layers of the table are live at once. The largest layer is the middle binomial coefficient, so this saves roughly a factor of three at n = 24 — again, about one and a half elements. - **Pruning unreachable masks.** When precedence constraints or capacity rules forbid most subsets, the live state count can fall far below 2^n. This is the only one of the three that can be worth an order of magnitude, and it depends entirely on the instance. - **Fixing a start point** to kill rotational symmetry — a factor of n, useful but not structural. None of these move the wall by more than a couple of elements. If the requirement is n = 35, engineering the same DP is not the answer; changing method is. ## The claim to state precisely "Exponential" is not a synonym for "slow" — at n = 12 this DP is instantaneous and beats anything cleverer. The honest statement is that the cost multiplies by two per element, that memory rather than time is the binding constraint, and that the crossover from trivial to impossible happens inside a range of about eight elements. Knowing *where* that range sits is the difference between choosing the technique correctly and discovering the wall in production.
- If n = 24 and memory is the binding constraint, what can you actually do?Shrink entries (two-byte costs instead of eight), keep only two layers live if every transition adds exactly one element, prune masks the constraints make unreachable, and fix a start point to kill symmetry. Together those are a small constant factor — maybe two elements of headroom. If you need materially more, the method has to change, not its memory layout.
- Does an asymmetric cost matrix change the complexity?No. The state count and transition count depend only on n, so both stay 2^n·n and 2^n·n^2. What asymmetry costs you is reuse: you can no longer reverse a partial sequence and claim the same cost, which rules out symmetry-based halving and some pruning tricks. The wall sits in the same place either way.
Folding a sheet of paper in half is easy seven times and impossible at fifty; nothing changes about the method, only the count of folds.
saying these in an interview costs you the question
- Says exponential state space is fine up to about n = 30
- Quotes the transition count but never the memory footprint
- Treats going from 20 to 30 elements as a 1.5x increase
- Believes a faster machine or more threads moves the ceiling
- Confuses the exponent: thinks the table is n^2 not 2^n