Knuth, CACM 1984

This is not actually the best example of how to link a paper to the rest of the wiki. Some other sample papers are Turney, ACL 2002 and Pang et al EMNLP 2002

Citation

Knuth, D.E., 1984, The complexity of songs, in the April special issue of Communications of the ACM.

Online version

I couldn't find an archival version online, but a copy is available here [1]

Summary

In this article, Knuth uses standard techniques from computational complexity to analyze the space complexity of various types of songs. The main results given are:

• Adding a repetitive refrain or chorus to a song reduces space complexity from N to cN, for c<1.
• A sequence of verses that is repeated in the pattern verse 1, verse 1 + verse 2, verse 1 + verse 2 + verse 3, ... (for example, the "12 days of Christmas") has space complexity O(sqrt(N)).
• A sequence of verses where each verse varies from the others in only in a single number, which is incremented or decremented in each verse (for example, "100 bottles of beer on the wall") has space complexity O(log(N)).
• Songs exist that have space complexity O(1) (e.g., many disco songs).

Comments and Questions

Are these results exploited in modern music compression schemes like MP3?

Wavelet compression is another commonly used compression scheme, but it is not discussed. Is there any followup work concerning it?

As far as I can tell the example given for the constant-space result is incorrect, since unpacking a song without a termination condition would result in a song that is infinitely long, not merely interminably long. A correct example might be The Song That Never Ends