A short post, but I have to post it. ‘The Complexity of Songs’ is a short communication Don Knuth wrote back in the 70s which is really quite interesting. It’s also a pretty funny joke.

The article capitalizes on the tendency of popular songs to evolve from long and content-rich ballads to highly repetitive texts with little or no meaningful content.

[...]

“…our ancient ancestors invented the concept of refrain” to reduce the space complexity of songs, which becomes crucial when a large number of songs is to be committed to one’s memory.

[...]

Finally, progress during the twentieth century—stimulated by the fact that “the advent of modern drugs has led to demands for still less memory”—leads to the ultimate improvement: Arbitrarily long songs with space complexity O(1), e.g. for a song to be defined by the recurrence relation.

We’ve really taken the concept to heart in modern popular music haven’t we? See here for explanation and here for the original paper.

Cheers.