In his paper ”The complexity of songs”, Knuth introduced the notion of the space complexity of a song and used it to account for music history. For example, compared to a song whose lyrics must be memorized verbatim, a song with a refrain has its space complexity reduced by a constant factor. To justify the quest for songs with reduced space complexity, Knuth appeals to cognitive science:
It is known [3] that almost all songs of length n require a text of length ~ n. But this puts a considerable space requirement on one’s memory, if many songs are to be learned; hence our ancient ancestors invented the concept of a refrain [14].
Knuth proceeds to give many examples of songs of differing space complexity, including ”m bottles of beer on the wall”, which has space complexity O(log n) because the song of m verses has length n = Θ(m log m) but can be defined in space O(log m). (The “log m” in ”m log m” is because it takes Θ(log m) words to name each m in English.)
There are actually two quantities that can be reasonably called the space complexity of a song. First, there is the length of the shortest program that generates the song, akin to Kolmogorov complexity. In cognitive-science terms, this is the amount of long-term memory needed to store the song for future recall. Second, there is the space required to generate the song, akin to the space complexity of an algorithm. In cognitive-science terms, this is the amount of short-term memory needed to perform the song. For many songs, the long-term and short-term space complexities coincide. This is the case for ”m bottles of beer on the wall”.
Which of the two notions did Knuth have in mind? On one hand, his citation ”[3]” above refers to Chaitin’s paper “On the length of programs for computing finite binary sequences: statistical considerations”. So, I would say long-term. On the other hand, after explaining how ”m bottles of beer on the wall” witnesses that there exist songs of complexity O(log n), Knuth failed to make the obvious further remark that “10m−1 bottles of beer on the wall” witnesses that there exist songs of (long-term) complexity O(log log n)”. So, I would say short-term.
Below is another set of lyrics with long-term space complexity O(log log n) but short-term space complexity O(log n). I think its use of the A-not-A construction is more natural than restricting bottle counts to numbers of the form 10m−1, but you may disagree. I’ll leave translation into English as an exercise.
這首歌
是指數成長
不是指數成長？
（指數～指數～～
成長～成長～～喔～～
指數～指數～～
成長～成長～～喔～～）
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長？
（指數～指數～～
成長～成長～～喔～～
指數～指數～～
成長～成長～～喔～～）
我會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長
不會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長？
（指數～指數～～
成長～成長～～喔～～
指數～指數～～
成長～成長～～喔～～）
他好奇
我會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長
不會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長
不好奇
我會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長
不會問
你知道
這首歌
是指數成長
不是指數成長
不知道
這首歌
是指數成長
不是指數成長？
（指數～指數～～
成長～成長～～喔～～
指數～指數～～
成長～成長～～喔～～）