When writing a song about a collection of items, there are many possible ways to describe the collection, resulting in many possible relationships between the size of the collection and the length of the song. Here, we catalog the different complexity classes of songs, and provide example songs in each complexity class.
B (Boring) - O(1)
Any song which doesn’t include numbers or lists.
Too many to list, go find one yourself
HM (How Many) - O(log n)
States the number of items, but doesn’t list them individually.
L (List) - O(n)
Lists out each item without numbering them.
- 88 Lines About 44 Women - The Nails
C (Count) - O(n log n)
Lists out each item, including a number.
- 99 Bottles of Beer - traditional
CL (Cumulative List) - O(n2)
Lists out each item along with all the items that came before it, but without numbers.
- The Rattlin’ Bog - traditional
- Chad Gadya - traditional
- Why We Build The Wall - Anaïs Mitchell
CC (Cumulative Count) - O(n2 log n)
Lists out each item along with all the items that came before it, including numbers for every item.
- The Twelve Days of Christmas - traditional
- Echad Mi Yodea - traditional
- Come When I Call You - Woody Guthrie
DL (Doubling List) - O(2n)
Lists out each item, and each item takes twice as long to describe as the previous item.
- Telnet Song - Guy Steele
My friend V— argues that, since for many values of g there does not exist any finite simple group of order g, the complexity of this song may be greater than O(log n). For instance, since there’s no finite simple group of order 4, the hypothetical song Finite Simple Group (of Order Five) should be considered the fourth element of the Finite Simple Group family of songs. Thus, letting f(n) be the order of the nth-smallest finite simple group, the complexity would be O(log f(n)).
I strongly disagree with this assessment, for multiple reasons. First, I think that the nonexistence of a finite simple group of order 4 doesn’t imply the nonexistence of the song Finite Simple Group (of Order Four); the song would be mathematically incorrect, but the rest of the lyrics aren’t any better, and this line of thinking would seem to completely remove The Twelve Days of Christmas from the scope of our analysis. Furthermore, even if we accept that songs with logically inconsistent values of n should be excluded, I believe that song families should be thought of as partial functions from non-negative integers to songs, rather than ordered collections of songs. Thus, regardless of whether Finite Simple Group (of Order Four) exists, Finite Simple Group (of Order Five) should be regarded as the n=5 case.
I will refer to my definition of song complexity, where song length is considered as a function of a number or the size of a list that appears in the song, as parametric complexity; and to V—’s definition, where song length is considered as a function of a song’s position in a list of possible songs, as ordinal complexity. To demonstrate the superiority of parametric complexity over ordinal complexity, I plan to write a song called Six is a Busy Beaver Number; the song will have parametric complexity O(log n), and uncomputable ordinal complexity. ↩
One could argue that this song should be in L rather than HM, since it lists out the elements of the group (“me and you”). It depends whether a polyamorous version such as Finite Simple Group (of Order Three) would say “me and you and you” or just “all of us”; this is a difficult decision, as the former doesn’t scan and the latter doesn’t rhyme. We leave this question to the reader as an exercise. ↩