The Song Complexity Zoo
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.
Examples
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.
Examples
 Seasons of Love  Jonathan Larson
 Finite Simple Group (of Order Two)^{1}^{2}  The Klein Four
L (List)  O(n)
Lists out each item without numbering them.
Examples
 88 Lines About 44 Women  The Nails
C (Count)  O(n log n)
Lists out each item, including a number.
Examples
 99 Bottles of Beer  traditional
CL (Cumulative List)  O(n^{2})
Lists out each item along with all the items that came before it, but without numbers.
Examples
 The Rattlin’ Bog  traditional
 Chad Gadya  traditional
 Why We Build The Wall  Anaïs Mitchell
CC (Cumulative Count)  O(n^{2} log n)
Lists out each item along with all the items that came before it, including numbers for every item.
Examples
 The Twelve Days of Christmas  traditional
 Echad Mi Yodea  traditional
 Come When I Call You  Woody Guthrie
DL (Doubling List)  O(2^{n})
Lists out each item, and each item takes twice as long to describe as the previous item.
Examples
 Telnet Song  Guy Steele
Footnotes

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 nthsmallest 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 nonnegative 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. ↩