The complexity of songs
Over 20 years ago, Computer Science Icon Donald Knuth published his in depth analysis of the complexity of song lyrics: The Complexity of Songs. In this paper, Professor Knuth traces the efforts of lyricists over the ages as they seek to reduce the amount of memory required to represent a (seemingly) complex and interesting set of verses. First, Knuth gives us the basic lemma and proof and then begins with the historical survey showing how the lyric complexity has been slowly reduced from N (the song length) to N^(1/2) (old MacDonald) and 1 / log(n)^(1/2) for 'the 12 days of Christmas'. The big breakthrough of course occurred with the "m Bottles of Beer on the wall" that reduced lyric complexity to O(log n). Knuth concludes with an analysis of the latest attempts (as of 1984) in lyric complexity reduction by Mr KC of the sunshine band (uh huh uh huh).
SunLabs' Guy Steele has continued to push ahead with this area of research. He has produced the Telnet song with a complexity that approaches O(1).