Intuitively I'd say a human pairing socks is far better than O(n2) because finding something that matches a given sock is close to O(1) on small sets.