FANDOM



"The Complexity of Songs" was a journal article published by computer scientist Donald Knuth in 1977,[1] as an in-joke about computational complexity theory. The article capitalizes on the tendency of popular songs to evolve from long and content-rich ballads to highly repetitive texts with little or no meaningful content.[2] The article notes how some songs can reach a complexity level, for a song of length N words, as formula: O(log N). The gist of the article is repeated, below, maintaining the wit of the key concepts.

Article summary

Knuth writes, with a grain of truth, that "our ancient ancestors invented the concept of refrain" to reduce the space complexity of songs, which becomes crucial when a large number of songs is to be committed to one's memory. Knuth's Lemma 1 states that if N is the length of a song, then the refrain decreases the song complexity to cN, where the factor c < 1.[1]

Knuth further demonstrates a way of producing songs with O(\sqrt N) complexity, an approach "further improved by a Scottish farmer named O. MacDonald".[1]

More ingenious approaches yield songs of complexity O(\log N), a class known as "m bottles of beer on the wall".

Finally, the progress during the 20th century—stimulated by the fact that "the advent of modern drugs has led to demands for still less memory"—leads to the ultimate improvement: arbitrarily long songs with space complexity O(1), e.g. for a song to be defined by the recurrence relation[1]

S_0=\epsilon, S_k = V_kS_{k-1},\, k\ge 1,
V_k = 'That's the way,' U 'I like it,' U, for all  k \ge 1
U= 'uh huh,' 'uh huh'

Further results

Prof. Kurt Eisemann of San Diego State University in his letter to the Communications of the ACM[3] further improves the latter seemingly unbeatable estimate. He begins with an observation that for practical applications the value of the "hidden constant" c in the Big Oh notation may be crucial in making the difference between the feasibility and unfeasibility: for example a constant value of 1080 would exceed the capacity of any known device. He further notices that a technique has already been known in Mediaeval Europe whereby textual content of an arbitrary tune can be recorded basing on the recurrence relation S_k = C_2S_{k-1}, where C_2 = 'la', yielding the value of the big-Oh constant c equal to 2. However it turns out that another culture achieved the absolute lower bound of O(0)! As Prof. Eisemann puts it:

"When the Mayflower voyagers first descended on these shores, the native Americans proud of their achievement in the theory of information storage and retrieval, at first welcomed the strangers with the complete silence. This was meant to convey their peak achievement in the complexity of songs, namely the demonstration that a limit as low as c=0 is indeed obtainable."

However the Europeans were unprepared to grasp this notion, and the Indian chiefs, in order to establish a common ground to convey their achievements later proceeded to demonstrate an approach described by the recurrent relation S_k = C_1S_{k-1}, where C_1 = 'i', with a suboptimal complexity given by c=1.[2][3]

References

  1. 1.0 1.1 1.2 1.3 Knuth, D. "The Complexity of Songs", SIGACT News, Summer 1977, 17–24.
  2. 2.0 2.1 Steven Krantz (2005) "Mathematical Apocrypha Redux", ISBN 0-88385-554-2, pp.2, 3.
  3. 3.0 3.1 Kurt Eisemann, "Further Results on the Complexity of Songs", Communications of the ACM, vol 28 (1985), no. 3, p. 235.

External links


Donald Knuth
Publications
Software
  • [[TeX|TeX
This article uses material from the Wikipedia article The Complexity of Songs, that was deleted or is being discussed for deletion, which is released under the Creative Commons Attribution-ShareAlike 3.0 Unported License.
Author(s): EmilJ Search for "The Complexity of Songs" on Google
View Wikipedia's deletion log of "The Complexity of Songs"
Wikipedia-logo-v2
]]
Fonts
Literate programming
Algorithms
Other
This article uses material from the Wikipedia article The Complexity of Songs, that was deleted or is being discussed for deletion, which is released under the Creative Commons Attribution-ShareAlike 3.0 Unported License.
Author(s): DenisKrivosheev Search for "The Complexity of Songs" on Google
View Wikipedia's deletion log of "The Complexity of Songs"
Wikipedia-logo-v2
de:The Complexity of Songs

ru:Оценка сложности песен

This article uses material from the Wikipedia article The Complexity of Songs, that was deleted or is being discussed for deletion, which is released under the Creative Commons Attribution-ShareAlike 3.0 Unported License.
Author(s): הסרפד Search for "The Complexity of Songs" on Google
View Wikipedia's deletion log of "The Complexity of Songs"
Wikipedia-logo-v2

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.