View source for The Complexity of Songs

{{Short description|1977 scholarly article by Donald Knuth}}
'''"The Complexity of Songs"''' is a [[scholarly article]] by [[computer scientist]] [[Donald Knuth]] published in 1977<ref name=knu /> as an [[in-joke]] about [[computational complexity theory]]. The article capitalizes on what it argues is the tendency of popular [[song]]s to devolve from long and content-rich [[ballad]]s to highly repetitive texts with little or no meaningful content.<ref name=redux>Steven Krantz (2005) "Mathematical Apocrypha Redux", {{ISBN|0-88385-554-2}}, pp.2, 3.</ref> The article states that a song of length ''N'' words may be produced remembering, e.g., only {{nowrap|[[Big O notation|O]]([[logarithm|log]] ''N'')}} words ("[[space complexity]]" of the song) or even less.

== Article summary ==
Knuth writes 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 (mathematics)|Lemma]] 1 states that if ''N'' is the length of a song, then the refrain decreases the song complexity to ''cN'', where the factor&nbsp;{{math|''c'' < 1}}.<ref name="knu">{{cite journal | last=Knuth | first=Donald | title=The Complexity of Songs | journal=ACM SIGACT News | date=Summer 1977 | volume=9 | issue=2 | pages=17–24| doi=10.1145/1008354.1008355 | s2cid=17533775 | doi-access=free }}
Reprinted in: {{cite journal | last=Knuth | first=Donald | title=The Complexity of Songs | journal=[[Communications of the ACM]] | year=1984 | volume=27 | issue=4 | pages=344–346 | doi=10.1145/358027.358042 | mr=784131| doi-access=free }}</ref>

Knuth further demonstrates a way of producing songs with {{math|[[Big O notation|''O'']]({{sqrt|''N''}})}} complexity, an approach "further improved by a [[Scottish people|Scottish]] farmer named [[Old McDonald Had a Farm|O. MacDonald]]".<ref name=knu />

More ingenious approaches yield songs of complexity <math>O(\log N)</math>, a class known as "[[99_Bottles_of_Beer#References_in_computer_science|''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 {{tmath|O(1)}} exist, e.g. a song defined by the [[recurrence relation]]<ref name=knu />

:<math>S_0=\epsilon, S_k = V_kS_{k-1},\, k\ge 1,</math>
:{{math|1=''V''{{sub|''k''}} =}} '[[That's the Way (I Like It)|That's the way]],' {{mvar|U}} 'I like it,' {{mvar|U}}, for all {{math|k &ge; 1}}
:{{math|1={{var|U}} =}} 'uh huh,' 'uh huh'

== Further developments ==
Prof. Kurt Eisemann of [[San Diego State University]] in his letter to the ''[[Communications of the ACM]]''<ref name=kurt /> 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 O notation|big ''O'']] notation may be crucial in making the difference between the feasibility and unfeasibility: for example a constant  value of 10<sup>80</sup> 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 <math>S_k = C_2S_{k-1}</math>, where <math>C_2 = \texttt{'la'}</math>, yielding the value of the big-''O'' constant ''c'' equal to 2. However it turns out that another culture achieved the absolute lower bound of ''O''(0). As Prof.&nbsp;Eisemann puts it:
<blockquote>
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''&nbsp;=&nbsp;0 is indeed obtainable.
</blockquote>

It is then claimed that the Europeans were unprepared to grasp this notion, and the [[Indian chief|chiefs]], in order to establish a common ground to convey their achievements later proceeded to demonstrate an approach described by the recurrent relation <math>S_k = C_1S_{k-1}</math>, where <math>C_1 = \texttt{'i'}</math>, with a suboptimal complexity given by {{math|''c'' {{=}} 1}}.<ref name=redux /><ref name=kurt>{{cite journal | doi=10.1145/3166.315004 | title=ACM forum | date=1985 | last1=Ashenhurst | first1=Robert L. | journal=Communications of the ACM | volume=28 | issue=3 | pages=235–240 }}</ref>

The ''O''(1) space complexity result was also implemented by [[Guy L.&nbsp;Steele, Jr.]], "perhaps challenged by Knuth's [article]."<ref>{{cite journal | doi=10.1145/358027.358040 | title=A further view of the first quarter century | date=1984 | last1=Neumann | first1=Peter G. | journal=Communications of the ACM | volume=27 | issue=4 | page=343 }}</ref> Dr.&nbsp;Steele's ''[[TELNET]] Song'' used a completely different algorithm based on exponential recursion, a parody on some implementations of TELNET.<ref>{{cite journal | doi=10.1145/358027.1035691 | title=THE TELNET SONG: ("Control-Uparrow Q.") | date=1984 | last1=Steele | first1=Guy L. | journal=Communications of the ACM | volume=27 | issue=4 | pages=347–348 }}</ref><ref>[http://www.poppyfields.net/filks/00222.html Text of the TELNET Song] (retrieved January 5, 2012).</ref><ref>[http://www.eskimo.com/~nickz/dec/telnet-song.mid Telnet song in MIDI format].</ref>

Darrah Chavey suggested that the complexity analysis of human songs can be a useful pedagogic device for teaching students complexity theory.<ref name=Chavey1996>{{cite conference |last=Chavey |first=Darrah |title=Proceedings of the twenty-seventh SIGCSE technical symposium on Computer science education |chapter=Songs and the analysis of algorithms |year=1996 |pages=4–8 |doi=10.1145/236452.236475 |isbn=089791757X |s2cid=148247 |chapter-url=http://dl2.acm.org/citation.cfm?id=236475&CFID=248220371&CFTOKEN=72224448 |accessdate=7 January 2013}}</ref>

The article "On Super[[polylogarithmic]] [[subexponential time|Subexponential]] Functions" by Prof.&nbsp;[[Alan Sherman]]<ref>{{cite journal |doi=10.1145/122413.990652 |doi-access=free |title=On Superpolylogarithlnic Subexponential Functions (Part I) |date=1991 |last1=Sherman |first1=Alan T. |journal=ACM SIGACT News |volume=22 |page=65 }}</ref> writes that Knuth's article was seminal for analysis of a special class of functions.

== References ==
{{Reflist}}

== External links ==
* "[http://www.cs.bme.hu/~friedl/alg/knuth_song_complexity.pdf The Complexity of Songs]", Knuth, Donald E. (1984).

{{Donald Knuth navbox}}

{{DEFAULTSORT:Complexity Of Songs}}
[[Category:Computational complexity theory]]
[[Category:Mathematics of music]]
[[Category:In-jokes]]
[[Category:Computer humour]]
[[Category:Donald Knuth]]
[[Category:1977 documents]]
[[Category:Computer science papers]]
[[Category:Music and humour]]