"The Complexity of Songs" is a scholarly article by computer scientist Donald Knuth in 1977,[1] as an in-joke about computational complexity theory. The article capitalizes on what it argues is 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) or even less.
knu
was invoked but never defined (see the help page).