Quadratic Songs and Books

quad-ballsMy son is 2 1/2 years old, and loves stories.  His favorite book at the moment is A Fly Went By.

In the book, a boy sits lazily by the lake and observes a fly passing.  The fly in turn is pursued by a frog, who is in turn chased by a cat, and so on.

Each animal introduced is pursued by yet another, and a pattern emerges in the story.  For each new animal

  • The animal is introduced
  • All the prior animals are again enumerated

In this manner, following the introduction of the dog, the story goes:

The fly ran away in fear of the frog
who ran from the cat, who ran from the dog …

Cumulative Stories

This style in song form is called cumulative, and other examples include the familiar Twelve Days of Christmas, for which on day three we have

On the third day of Christmas, my true love gave to me…
3 French Hens
2 Turtle Doves
And a Partridge in a Pear Tree.

Yet another similar example is the song There Was And Old Lady Who Swallowed a Fly.  After swallowing a bird, spider and fly, the song goes

There was an old lady who swallowed a bird.
How absurd to swallow a bird.
She swallowed the bird to catch the spider,
that wiggled and wiggled and tickled inside her.
She swallowed the spider to catch the fly.
I don’t know why she swallowed the fly.
I guess she’ll die.

Each has a similar pattern.

Quadratic Behavior

With some amusement one evening while reading A Fly Went By, I realized that this style exhibits quadratic behavior.  That is, the length of the song/story increases with the square of the number of actors/stanzas. 

This is evident due to the number of actors/stanzas enumerated in each of the N segments in sequence:

1
2
3

N

Arranged with an equivalent number of objects (dots, for example) on each line, the sequence forms a half-triangle pattern, as pictured at the top of this article.

If you accumulate all the sizes of all the segments, we have the numerical series

1 + 2 + 3 + … + N  =  N (N+1) / 2

which, for large N, is dominated by the term N2.  In computer science, an accumulation like this is frequently an indication of non-ideal algorithm design.

What’s The Bottom Line?

In summary, if you double the number of actors / stanzas, the resulting book / song will be not twice, but four times as long.  “24 days of Christmas” would be an excruciating 4 times as tedious to listen to, relative to the (already tedious) 12 days.

It isn’t very surprising, then, that these songs and books generally tend to call it quits after 8-12 segments.

In the future, my interview questions may include children’s books.

This entry was posted in Software. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>