On a more practical note but along a related thread, a couple of years ago I threw out all of my socks and bought a stack of the exact same plain black socks. Now I never have to worry about matching socks, when a hole appears I just throw that sock out, when I'm getting low on socks I throw out the lot and buy them new.
This particular problem appears to be close to being solved for me. I don't see a value in subscription, but reliable source of getting same high quality (providing test socks are going to high-quality) socks of the same color/design in bundles repeatedly is definitely a win.
I do too. One pool of identical whites and one of blacks. Moves the matching problem from O(n) to O(1) and it's ok if you lose an odd one here or there.
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.
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.
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.
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.
I tried this until I noticed that the socks from the same brand are a slightly different color across packs. Now I have the problem of trying to match 12 pairs of gray socks that are mostly a different shade of gray.
