> If the largest cost in your new way is constant, and *any* cost in
> the existing way is n^2, you win. :^>

Not quite.  As you point out elsewhere, it depends on the constant
factors.  Indeed, since there is a fixed maximum PID, theoretically,
any way is O(1) because it is dominated by whatever the worst case is
over the (finite!) set of all possible used/unused PID distributions.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       mouse@rodents.montreal.qc.ca
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B