No. In order for the algorithm to report that a set with N elements contains an item x, it must find that both sparse[x] < N and dense[sparse[x]] = x; this cann

No. In order for the algorithm to report that a set with N elements contains an item x, it must find that both sparse[x] < N and dense[sparse[x]] = x; this cannot happen unless x is actually in the set, because dense[0...N-1] has been initialized during the insertion of the first N elements.