[VBprogrammer]

Given that my socks are partitioned into two sets (washing basket and drawer) and as I mentioned above I would throw them out if the failure rate became high enough to impact the asymptotic behavior I'd say that O(1) is probably correct.

[mathattack]

If a sock has a hole, it gets tossed.

Now that I think of it, the mixed sock problem can actually be worse than O(n^2). For instance, if I decide that I want to wear my Marvin the Martian socks, and can only find one in the sock drawer, then it's a big problem. Look in the other drawers. Look under the bed. Look in the dryer. Repeat. Repeat. Until the other one is given up for lost.

[farnsworth]

It doesn't depend just on n since you aren't just searching through n available socks, you are searching k places with n_k socks in each place and with p_k confidence that you have thoroughly searched each place. I can't think of a more general problem that this might correspond to.

[mathattack]

Will it get solved when we straighten out this whole P NP business?