[Pat]: Which by definition is the same as O(Na) for suitable constants. Well, we don't know whether Na or Nb is larger - they may both be significant. It's premature to write off either one as a constant, I think - see below.
[Pat]: But in general, a HashSet/HashMap should be more of O(1) rather than O(n) Basic operations like add(), remove(), contains() are O(1). But operations like addAll() and removeAll() are obviously O(N). And of course, calling add(), contains() or remove() N times would be O(N).
The point is, if Na and Nb are of comparable size (call them both N), then the solutions given in this
thread are O(N^2), while a HashSet will be O(N). Big win.
[ October 28, 2008: Message edited by: Mike Simmons ]