Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 3 / d / ii

The original routine uses $O(1)$ auxiliary space and at most $O(N^2)$ membership work. A bitmap with universe size $M$ uses $\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 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.