= Combinatorial explosion
A combinatorial explosion is a rapid increase in the number of candidates generated by a search over combinations, often exponential or factorial in an input parameter. For example, listing all <subsets> of an $n$-element <set> produces $2^n$ candidates, while listing all <permutations> produces $n!$ candidates. In contrast, listing only fixed-size $q$-element <subsets> has <time complexity> at least $\binom nq=\Theta(n^q)$ for fixed $q$: potentially large, but polynomial rather than exponential in $n$.
Back to article page
