🔗 The Complexity of Songs

🔗 Computing 🔗 Computing/Software 🔗 Computing/Computer science

"The Complexity of Songs" is a journal article published by computer scientist Donald Knuth in 1977, 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. 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).