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.