The Complexity of Songs
Encyclopedia
"The Complexity of Songs" was an article published by Donald Knuth
, an example of an in-joke
in computer science
, namely, in computational complexity
theory. The article capitalizes on the tendency of popular song
s to evolve from long and content-rich ballad
s to highly repetitive texts with little or no meaningful content.
" 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 c < 1.
Knuth further demonstrates a way of producing songs with O
(
) complexity, an approach "further improved by a Scottish
farmer named O. MacDonald
".
More ingenious approaches yield songs of complexity O
(
), 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
'That's the way
,'
'I like it,' 
, for all 
'uh huh, uh huh'
in his letter to the Communications of the ACM
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
, where 
, yielding the value of the big-Oh constant c equal to 2. However it turns out that a culture more advanced than the European one achieved the absolute lower bound of O(0)! As Prof. Eisermann puts it:
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
, where 
, with a suboptimal complexity given by c=1.
Donald Knuth
Donald Ervin Knuth is a computer scientist and Professor Emeritus at Stanford University.He is the author of the seminal multi-volume work The Art of Computer Programming. Knuth has been called the "father" of the analysis of algorithms...
, an example of an in-joke
In-joke
An in-joke, also known as an inside joke or in joke, is a joke whose humour is clear only to people who are in a particular social group, occupation, or other community of common understanding...
in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, namely, in computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
theory. The article capitalizes on the tendency of popular song
Song
In music, a song is a composition for voice or voices, performed by singing.A song may be accompanied by musical instruments, or it may be unaccompanied, as in the case of a cappella songs...
s to evolve from long and content-rich ballad
Ballad
A ballad is a form of verse, often a narrative set to music. Ballads were particularly characteristic of British and Irish popular poetry and song from the later medieval period until the 19th century and used extensively across Europe and later the Americas, Australia and North Africa. Many...
s to highly repetitive texts with little or no meaningful content.
Article summary
With a grain of truth, Knuth writes that "our ancient ancestors invented the concept of refrainRefrain
A refrain is the line or lines that are repeated in music or in verse; the "chorus" of a song...
" to reduce the space complexity of songs, which becomes crucial when a large number of songs is to be committed to one's memory
Memory
In psychology, memory is an organism's ability to store, retain, and recall information and experiences. Traditional studies of memory began in the fields of philosophy, including techniques of artificially enhancing memory....
. Knuth's Lemma
Lemma (mathematics)
In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than as a statement in-and-of itself...
1 states that if N is the length of a song, then the refrain decreases the song complexity to cN, where c < 1.
Knuth further demonstrates a way of producing songs with O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(
) complexity, an approach "further improved by a ScottishScottish people
The Scottish people , or Scots, are a nation and ethnic group native to Scotland. Historically they emerged from an amalgamation of the Picts and Gaels, incorporating neighbouring Britons to the south as well as invading Germanic peoples such as the Anglo-Saxons and the Norse.In modern use,...
farmer named O. MacDonald
Old McDonald Had a Farm
"Old MacDonald Had a Farm" is a children's song and nursery rhyme about a farmer named MacDonald and the various animals he keeps on his farm. Each verse of the song changes the name of the animal and its respective noise. In many versions, the song is cumulative, with the noises from all the...
".
More ingenious approaches yield songs of complexity O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(
), a class known as "m bottles of beer on the wall99 Bottles of Beer
"99 Bottles of Beer" is a traditional song in the United States and Canada. It is popular to sing on long trips, as it has a very repetitive format which is easy to memorize, and can take a long time to sing. In particular the song is frequently sung by children on long bus trips, such as class...
".
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
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
'That's the wayThat's the Way (I Like It)
"That's the Way " is a song written by H.W. Casey and Richard Finch, and recorded and released in 1975 by KC and the Sunshine Band for their eponymous second album...
,'
'I like it,' , for all 'uh huh, uh huh'Further results
Prof. Kurt Eisemann of San Diego State UniversitySan Diego State University
San Diego State University , founded in 1897 as San Diego Normal School, is the largest and oldest higher education facility in the greater San Diego area , and is part of the California State University system...
in his letter to the Communications of the ACM
Communications of the ACM
Communications of the ACM is the flagship monthly journal of the Association for Computing Machinery . First published in 1957, CACM is sent to all ACM members, currently numbering about 80,000. The articles are intended for readers with backgrounds in all areas of computer science and information...
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
, where , yielding the value of the big-Oh constant c equal to 2. However it turns out that a culture more advanced than the European one achieved the absolute lower bound of O(0)! As Prof. Eisermann puts it:When the MayflowerMayflowerThe Mayflower was the ship that transported the English Separatists, better known as the Pilgrims, from a site near the Mayflower Steps in Plymouth, England, to Plymouth, Massachusetts, , in 1620...
voyagers first descended on these shores, the native AmericansNative Americans in the United StatesNative Americans in the United States are the indigenous peoples in North America within the boundaries of the present-day continental United States, parts of Alaska, and the island state of Hawaii. They are composed of numerous, distinct tribes, states, and ethnic groups, many of which survive as...
, proud of their achievement in the theory of information storage and retrieval, at first welcomed the strangers with the complete silenceSilenceSilence is the relative or total lack of audible sound. By analogy, the word silence may also refer to any absence of communication, even in media other than speech....
. 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
, where , with a suboptimal complexity given by c=1.External links
- "The Complexity of Songs", Knuth, Donald E. (1984).