= Solution
The original routine uses $O(1)$ auxiliary space and at most $O(N^2)$ membership work. A bitmap with universe size $M$ uses \b[$\Theta(M)$ extra storage and $\Theta(N)$ work in the <sequence>-generation loop] because membership and insertion each take constant time. Here the safe universal bound chooses $M=N(N-1)/2+1$, so extra storage is $\Theta(N^2)$ for growing $N$.
Initialization must be accounted for separately: creating and clearing a Boolean <array> of length $M$ takes $\Theta(M)$ work in the usual <array>-initialization model. Consequently \b[the complete one-shot routine takes $\Theta(M+N)$], which is $\Theta(N^2)$ with this conservative universe bound. The faster lookup does not make that quadratic setup disappear. If the bitmap is already initialized, or the analysis explicitly charges only the generation phase, the remaining phase is linear. A tighter known bound on values can reduce the universe cost, but no unproved growth bound is needed here.
Back to article page
