Why you should always pair your socks straight out of the wash



Feb 24, 2024

Pairing your socks after washing them seems like an annoying and unnecessary task. You think you can just find pairs as and when you need them, you could either do all the work now, or just spread it out over the next couple of weeks.

It turns out that, for more than 2 pairs of socks, it is always quicker to pair all your socks at once rather than one at a time.


For this post I will assume that all pairs of socks are unique in their pattern.

To make it possible to write about socks I am going to use numbers to refer to specific socks (sock 1, sock 2, etc.), and letters to refer to patterns of socks (sock pattern A, sock pattern B, etc.)

Worst cases

It is usually helpful in discussions like this to start with the worst case scenario. After all, you could get incredibly lucky and always pull out 2 socks that match, but, to understand just how lucky that would be, we need to know how bad it could have been.

If I have 5 unique pairs of socks (so 10 socks) all jumbled up, and I would like to find a single matching pair, the steps could look something like this:

  1. Pick out a sock (sock 1), which we take to be part of our pair
  2. Pick out another sock (sock 2)
  3. If sock 1 matches sock 2 then we are finished, otherwise go back to step 2

What is the most socks I could have to look at (including sock A) before I find my matching pair?


Say we have 5 pairs of socks, with patterns A, B, C, D, E

If I pick up socks in the following order: A, B, B, C, C, D, D, E, E, A

I will have to go through all 10 socks before I find a pair

Expressing things formally (Big-O notation)

If we have 10 socks we could have to go through a maximum of 10 socks to find a pair. Similarly, for 20 socks, we could have to go through all 20 socks to find a pair. This is true for any number of socks. It is useful to know how the number of steps scales with the number of socks, and therefore how long it could take to find a pair.

We can express this as a formula: t=st = s (where tt is the time taken, and ss is the number of socks). This means that the time taken scales linearly with the number of socks. We could also write this as t=12pt = \frac{1}{2} p (where pp is the number of pairs of socks).

In both cases here, the time taken is proportional to the number of socks, and so we can say that the time taken is "of the order of O(s)O(s)", or O(p)O(p), or more commonly O(n)O(n), where nn is a stand in for any input variable.

The phrasing "of the order of" is irrelevant, people often say "has an order of", or even just shorten it to "this algorithm is O(n)O(n)"; the interesting part is O(n)O(n).

OO (as in Big O) tells us that whatever is in the brackets is the worst case.

Then the nn is the really important part. It refers to the input of your system, essentially whatever can scale. In our case nn refers to the number of socks (or pairs of socks). We can increase the number of socks, which will increase the time taken to find a pair.

Here, because the time taken scales linearly with the number of socks, we write O(n)O(n). If we had a task that took 4 actions for 2 socks, 9 actions for 3 socks, 16 actions for 4 socks, etc. then this is likely O(n2)O(n^2).

Also note that we said O(p)O(p) not O(12p)O(\frac{1}{2} p) because any constant factor is ignored. This is because we are only interested in how the time taken scales with the number of socks, not the exact time taken.

Average and best cases

If we know the best case (22), and the worst case (nn), and we assume that the probability of falling anywhere between those values is uniform, then we can find the average case.

onepair(n)=n+22=12n+1\begin{aligned} onepair(n) &= \frac{n + 2}{2} \\ &= \frac{1}{2}n + 1 \end{aligned}

For the average case we use Θ\Theta instead of 00, so we say it has an order of Θ(n)\Theta(n) (note that we have dropped the factor of 12\frac{1}{2}, and the + 1).

For the best case we use Ω\Omega, so we say it has an order of Ω(1)\Omega(1) (for any constant 2,73,x2, 73, x etc., we just use 11).

When we're designing algorithms it's generally useful to think in terms of the average case (although outliers in the best or worst cases can cause problems so don't fully ignore them).

Unfortunately people often seem just use OO to refer to all three cases (or often the average case), but it's useful to know the difference.

Pairing n socks

If we have 10 socks, and we find one pair, on average this will take 10+22=6\frac{10 + 2}{2} = 6 steps. From the remaining 8 socks, to find another pair will take 8+22=5\frac{8 + 2}{2} = 5 steps. For 6: 44, for 4: 33, for 2: 22. This gives us a total of 6+5+4+3+2=206 + 5 + 4 + 3 + 2 = 20 steps.

Can you see a pattern here?


This is equivalent to the sum of the numbers 2 to 6.

Or, for <La Tex="n" /> socks, the sum of the numbers 2 to 0.5n + 1.

The formula for 1+2++x1 + 2 + \cdots + x is

a=1xa=12x(x+1)\sum_{a = 1}^{x} a = \frac{1}{2}x(x + 1)

So to find (n2+1)+(n2)++2(\frac{n}{2} + 1) + (\frac{n}{2}) + \cdots + 2 we use

allpairs(n)=a=2n2+1a=(a=1n2+1a)1=12(n2+1)(n2+2)1\begin{aligned} allpairs(n) &= \sum_{a = 2}^{\frac{n}{2} + 1} a \\ &= \left( \sum_{a = 1}^{\frac{n}{2} + 1} a \right) - 1 \\ &=\frac{1}{2}(\frac{n}{2} + 1)(\frac{n}{2} + 2) - 1 \end{aligned}

This looks annoying, but let's expand it out:

allpairs(n)=18n2+34nallpairs(n) = \frac{1}{8}n^{2} + \frac{3}{4}n

And given we only care about the average case, we can drop the factor on n2n^{2} and the nn term, and just have

allpairs(n)=Θ(n2)allpairs(n) = \Theta(n^{2})

Pairing n socks out of N

If we want to pair 100 socks, we can find how long it will take. What if we just want to pair 10 socks out of 100?

We know to pair 2 socks out of 100 we can use onepair(100)=12n+1=51onepair(100) = \frac{1}{2}n + 1 = 51, similarly 2 socks out of 99: 50, 98: 49, etc.

So to pair 10 socks out of 100 we need 51+50+49+48+47=24551 + 50 + 49 + 48 + 47 = 245.

How can we figure this out quicker? It's the same as doing allpairs(100)allpairs(90)allpairs(100) - allpairs(90).

We can check this:

allpairs(100)=12(1002+1)(1002+2)1allpairs(90)=12(902+1)(902+2)1allpairs(100)allpairs(90)=13251080=245\begin{aligned} allpairs(100) &= \frac{1}{2}(\frac{100}{2} + 1)(\frac{100}{2} + 2) - 1 \\ allpairs(90) &= \frac{1}{2}(\frac{90}{2} + 1)(\frac{90}{2} + 2) - 1 \\ allpairs(100) - allpairs(90) &= 1325 - 1080 \\ &= 245 \end{aligned}

So we can say that to pair nn socks out of NN is found by

somepairs(N,n)=allpairs(X)allpairs(Xx)=(18N2+34N)(18(N2)2+34(Nn))=(18N2+34N)(18N214nN+18n2+34N34n)=(18N218N2)+(34N34N)(14nN+18n234n)=14nN18n2+34n\begin{aligned} somepairs(N, n) &= allpairs(X) - allpairs(X - x) \\ &= \left( \frac{1}{8} N^{2} + \frac{3}{4} N \right) - \left( \frac{1}{8} (N - 2)^{2} + \frac{3}{4} (N - n) \right) \\ &= \left( \frac{1}{8} N^{2} + \frac{3}{4} N \right) - \left( \frac{1}{8} N^{2} - \frac{1}{4} nN + \frac{1}{8} n^{2} + \frac{3}{4} N - \frac{3}{4} n \right) \\ &= \left( \frac{1}{8} N^{2} - \frac{1}{8} N^{2} \right) + \left( \frac{3}{4} N - \frac{3}{4} N \right) - \left( - \frac{1}{4} nN + \frac{1}{8} n^{2} - \frac{3}{4} n \right) \\ &= \frac{1}{4} nN - \frac{1}{8} n^{2} + \frac{3}{4} n \end{aligned}

Sanity check

nn is necessarily less than or equal to NN, because you can't pair more socks than you have, so the worst case is when n=Nn = N. If we sub this in, we find

somepairs(N,N)=14nN18n2+34n=14N218N2+34N=18N2+34N=allpairs(N)\begin{aligned} somepairs(N, N) &= \frac{1}{4} nN - \frac{1}{8} n^{2} + \frac{3}{4} n \\ &= \frac{1}{4} N^2 - \frac{1}{8} N^{2} + \frac{3}{4} N \\ &= \frac{1}{8} N^2 + \frac{3}{4} N \\ &= allpairs(N) \end{aligned}

That makes sense!

The core of the argument

So we can say

somepairs(N,n)=Θ(Nn)somepairs(N, n) = \Theta(Nn)

Is that good?

As we've seen, nNn \le N, so NnN2Nn \le N^{2}. This means that the time taken to pair nn socks out of NN is guaranteed to be at most the time taken to pair NN socks, and the smaller nn is relative to NN, the more efficient it is to pair them as soon as they are out of the washing machine.

That is to say that the more socks you have, or the smaller your washing machine, the more efficient it is to pair them as soon as they are out of the washing machine.


Where is this time saving coming from?

Assume we have 9 pairs of socks, split into a 6 and a 3, with a guarantee that every sock is in the same set as its pair.

A grid showing required comparisons of socks

In the image above, in red are all the possible unsuccessful comparisons, and in green the successful ones. In reality, only half of the red comparisons will be done, because on average half-way through a comparison you will find a match.

In yellow are the comparisons that are not done, because they are between socks in different sets. This is a saving of 6×3=186 \times 3 = 18 comparisons.

And how do get two subsets with all pairs in the same one? If we assume socks are always worn in matching pairs, then the process of wearing and discarding pairs of socks achieves this!


There are lots more interesting things you could try to understand about this problem:

  • If I wanted to pair all NN socks, in chunks of nn, how many chunks would I need? (somepairs(N,n)+somepairs(Nn,n)+somepairs(N2n,n)+somepairs(N, n) + somepairs(N - n, n) + somepairs(N - 2n, n) + \cdots?)
  • In the "pair as you go" case, unless you're wearing all your socks then washing them all, the actual amount of checks is much worse than we have calculated because every nn pairs you wear, we reset back to NN socks to search through! How does that affect things?
  • On the other hand, the inclusion of duplicated patterns of socks would make the problem much easier, because you could just pair all the AA socks, then all the BB socks, etc.

But none of these detract from the fact that it is always quicker (or at least as fast if n=Nn = N) to pair your socks straight out of the wash, and that is a nice result to have.