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.
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'
Read more about this topic: The Complexity Of Songs
Famous quotes containing the words article and/or summary:
“In this great association we know no North, no South, no East, no West. This has been our pride for all these years. We have no political party. We never have inquired what anybody’s religion is. All we ever have asked is simply, “Do you believe in perfect equality for women?” This is the one article in our creed.”
—Susan B. Anthony (1820–1906)
“I have simplified my politics into an utter detestation of all existing governments; and, as it is the shortest and most agreeable and summary feeling imaginable, the first moment of an universal republic would convert me into an advocate for single and uncontradicted despotism. The fact is, riches are power, and poverty is slavery all over the earth, and one sort of establishment is no better, nor worse, for a people than another.”
—George Gordon Noel Byron (1788–1824)