The article capitalizes on what it argues is the tendency of popular songs to devolve from long and content-rich ballads to highly repetitive texts with little or no meaningful content.
[1] Knuth further demonstrates a way of producing songs with O(√N) complexity, an approach "further improved by a Scottish farmer named O.
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
exist, e.g. a song defined by the recurrence relation[1] 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 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
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.
It is then claimed that the Europeans were unprepared to grasp this notion, and the chiefs, in order to establish a common ground to convey their achievements later proceeded to demonstrate an approach described by the recurrent relation
[2][3] The O(1) space complexity result was also implemented by Guy L. Steele, Jr., "perhaps challenged by Knuth's [article].