scientific article
3 min read
fairly difficult
Article URL: Comments URL: Points: 1 # Comments: 0
"The Complexity of Songs" is a journal article published by computer scientist Donald Knuth in 1977,[1] as an in-joke about computational complexity theory. The article capitalizes on the tendency of popular songs to devolve from long and content-rich ballads to highly repetitive texts with little or no meaningful content.[2] The article notes that a song of length N words may be produced remembering, e.g., only O(log N) words ("space complexity" of the song).

Article summary [ edit ]

Knuth writes that "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. Knuth's Lemma 1 states that if N is the length of a song, then the refrain decreases the song complexity to cN, where the factor c < 1.[1]

Knuth further demonstrates a way of producing songs with O( N {\displaystyle {\sqrt {N}}} ) complexity, an approach "further improved by a Scottish farmer named O. MacDonald".[1]

More ingenious approaches yield songs of complexity O( log ⁡ N {\displaystyle \log N} ), a class known as "m bottles of beer on the wall".

Finally, the progress during the 20th century—stimulated by the fact that "the advent of modern drugs has led to demands for still less memory"—leads to the ultimate…
Contributors to Wikimedia projects
Read full article