[kylewpppd]

So I would argue that the matching problem with many different styles of socks is O(n^2), since we first must select one sock appropriate for the occasion, then rummage through all the other socks to select its match. This does have the problem that your algorithm may never finish if your laundry eats socks like mine does.

And that with all identical pairs, I assert the solution is O(n), since there is a chance that you will have to iterate through all of your socks to find one with no holes/is clean. However, I think the latter case is Omega(1). Not quite so sure about the first one.

[kragen]

Previous discussion of this question:

http://www.mail-archive.com/[e-mail]/msg0008...

http://news.ycombinator.com/item?id=1696125

[stralep]

If ordering is made by color&design, matching drops to O(n log(n)).

Again, with ordering, searching drops to O(log n)

[sid0]

However, that actually requires ordering socks, which as we all know is O(not gonna happen).

[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?