Computational Complexity, Explained Through Songs

If you’re reading this, you’ve probably heard of “computational complexity”, but you might not know what it is. Never fear! The Adder is here to help! I’ll walk you through what it is, and some common types, all through the lens of “how much memory power would it take to memorize the lyrics to this song?” And as a bonus, I’ll even cover “big O notation”!

First, the basics. Say you’ve written a computer program that calculates some algorithm. You want to know how long it’s going to run, or how much memory space it’s going to take up, or whatever. To do that, you’re going to need to know the size, in bits, of the input that’s going in.

What it means to have a space complexity of O(f(n)) (that’s your big O) means that if the input has n bytes, the algorithm will take f(n) memory space to run. “Memory space”, in this case, is sort of subjective and will depend on the specific machine you’re running your program on, but what programmers are generally interested in is how this scales with more input. For example, if your algorithm runs in O(2^n), it becomes very infeasible to run it on big input sizes.

Was that hard to understand? Let me try it in pictures:

Now, let’s change the x-axis from “input size” to “song length”. That’s right: We’re going to see how to minimize the brainpower needed to memorize a song. For help, and comic relief, we look to Donald Knuth’s “The Complexity of Songs”.

It is known that almost all songs of length n require a text of length ~ n. But this puts a considerable space requirement on one’s memory if many songs are to be learned; hence, our ancient ancestors invented the concept of a refrain. When the song has a refrain, its space complexity can be reduced to cn, where c < 1[…]

Donald Knuth

Essentially, what he is saying is that when you have a refrain in a song (which necessarily happens more than once), it adds text that you already memorized, saving memory power.

Knuth then goes on to describe songs of O(\sqrt{n}) complexity:

His song? Old McDonald Had a Farm.

Actually, he seems to have used an altered version of the song, so I’ll pass over it onto his other candidate, the shockingly cruel French song “Alouette“, here translated for the benefit of les personnes qui ne parlent pas le français:

La-a-a-ark, nice la-a-a-a-ark,
La-a-a-ark, I am going to pluck you.
I will pluck your ⟨something⟩, [double]
And your ⟨something else⟩ [again double]
And your ⟨everything that came in the previous verses⟩ [again double]
Aaah-aaah-aaah-aaah
[repeat]

The reason this requires less memory than an ordinary song with a refrain is that, in a regular song, the repetitive parts stay the same length. In “Alouette”, the repetitive part gets longer the more verses you have, because of the part that says “⟨everything that came in the previous verses⟩”. You have to repeat everything. (Although it seems pointless to pluck something that you already plucked.)

Can you make this better? As it turns out, yes!

A fundamental improvement was claimed in England in 1824, when the true love of U. Jack gave to him a total of 12 ladies dancing, 22 lords a-leaping, 30 drummers drumming, 36 pipers piping, 40 maids a-milking, 42 swans a-swimming, 42 geese a-laying, 40 golden rings, 36 collie birds, 30 french hens, 22 turtle doves, and 12 partridges in pear trees during the twelve days of Christmas.

Knuth, again

This comes to O(\sqrt{\frac{n}{\log n}}), but despite its cool-looking formula, it’s not really that much of an achievement, so we pass over that to “99 Bottles of Beer“.

This is a significant improvement! It comes to O(\log n), which is a lot better.

Why is this fundamentally better than “Alouette”, you ask? While “Alouette” had some structure beside the recursion, “99 Bottles” is essentially repeating a refrain over and over, slightly modified by the fact that each “refrain” uses a number which changes with every verse.

But can we do better than this?

Yes!

[T]he advent of modern drugs has led to demands for still less memory, and [it] has consequently just been announced: […] There exist arbitrarily long songs of complexity O(1).

Donald Knuth, yet again

Huh? you think. What kind of inane song would have the same lyrics even as the song got lengthened?

Well… this one. (Its only lyrics are “that’s the way”, “I like it”, and “uh huh”.)

Knuth ends his paper here, while forgetting to mention the absolute pinnacle of memory loss (that is, O(0)):

Classical music.