| The Complexity Of Songs |
Article Index for The |
Website Links For Complexity |
Information AboutThe Complexity Of Songs |
| CATEGORIES ABOUT THE COMPLEXITY OF SONGS | |
| computational complexity theory | |
| in-jokes | |
| computer humor | |
| donald knuth | |
|
With a grain of truth, 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 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. McDonald " (priority disputed). More ingenious approaches yield songs of complexity (1), e.g. for a song defined by the Recurrence Relation : : 'That's the way,' 'I like it,' , for all : 'uh huh,' 'uh huh' REFERENCES
|
|
|