Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 3 / e / Solution

The number isA direct search over every $q$-element subset must inspect $\left(\genfrac{}{}{0ex}{}{n}{q}\right)$ candidates. Testing one candidate by generating its subset sums creates $2^q$ values; storing previously seen sums detects a collision. Generating them incrementally needs $O(2^q)$ arithmetic operations, or $O(q{2}^q)$ for the straightforward independent calculation of each sum. Thus the simple overall search has cost on the scale of $\left(\genfrac{}{}{0ex}{}{n}{q}\right)2^q$, apart from integer-arithmetic and data-structure costs.

The important time complexity distinction is that fixed $q$ gives polynomial growth in $n$, of degree $q$, but this can still become impractically large. If $q$ increases with $n$, both the candidate count and the internal power set can grow exponentially. For example, near $q=n/2$ the binomial coefficient is already exponentially large. An exhaustive implementation can therefore encounter a combinatorial explosion; the fixed-$q$ estimate $\Theta (n^q)$ must not be described as exponential in $n$.