White socks

I try to get white socks in large batches. It’s a simple problem really. Finding a match for a sock is a function of the number of matches out of the total pool of socks. If a you buy a large batch of identical socks, then each sock matches every other sock, and finding a match is a simple constant time operation of O(1). This is both average case and worst case. If every pair is unique then you have an operation which is O(n) with average time O(n/2) and worst case O(n).

If you’ve got 100 socks and a sock matching test takes 1 second you’re saving 49 seconds every time you need to find a match. Realistically, it’s not quite that bad because you are frequently sorting as you go(and most people should do much better than 1 second per match test). But a full sort is still an O(n^2) operation so you need to avoid that whenever possible.

Looking at it from this standpoint the most algorithmically efficient solution is clear: buy only identical socks. How can fashion override basic principles of math and computer science?