Earlier quoted context omitted.
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. Unlike Jobs, nobody notices.
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…
Again, with ordering, searching drops to O(log n)