The Complexity Of Songs p3x2u

The Complexity of Songs Rohan Sharma 12 B Roll no.: 32 October 23, 2008

I’ll start with a few words of warning. Most of us want to give the “ideal talk.” This kind of talk begins with a good introduction to the topic of choice. It contains useful facts, but no theoretical information that the audience will find difficult to understand. Lastly, it lasts for less than ten minutes, as it’s not nice to eat other people’s time. I am not going to give an “ideal talk.” In fact, I intend to take it to the other extreme. I am going to discuss a small part of the field of computer science. So, my question to you is: what is computer science?. First of all, computer science is not “the study of computers.” It is the study of computation. It is also interesting to note that the natural sciences – physics, chemistry and biology – are neither prefixed nor suffixed by the word “science.” On the other hand, disciplines such as political science, moral science and – my personal favourite – computer science are not really sciences. Computer science is more of an art than a science. The veteran programmer Edsger Dijkstra once said “computer science is no more about computers than astronomy is about telescopes.” I will spend two minutes on boring stuff and the following five minutes on interesting stuff. So, kindly refrain from doing what our man here just did. Computational complexity is a branch of computer science concerned with analysing the time algorithms take to run on a system and the memory these algorithms take up. This analysis yields results that are valid for any machine an algorithm runs on; it could be a supercomputer or your wristwatch. Let’s start with something simple: how do we find the largest number in a list of integers? We use two pointers; the one on top traverses the entire list and the one below the list keeps track of the largest number we have found so far. So, if the length of the list is doubled, the pointer on top will need to walk twice as much as it did previously did. Hence, the time taken to find the largest number is also doubled. This gives us a linear relationship, and the algorithm is said to run in linear time, or have a complexity of O(n) (read as “big-oh of n”), which means that the running time is directly proportional to n, the length of the list. Next, we will analyse an algorithm called a binary search, which is essentially an ordered way of looking for a word in a dictionary. Suppose we have a sorted array and intend to search for a “target value.” We start by looking at the value in the middle of the array. If this value is equal to the target value, we’re done. If it’s greater than the target value, we can completely discard everything from the middle to the end of the array as all those values are clearly greater than the target value. Similarly, if it’s less than the target value, everything from the beginning 1

to the middle of the array. After doing this, lather, rinse, repeat. (This is similar to searching for a word in the dictionary by tearing one half of the dictionary if the word we want to find is not seen the page we are looking at.) If the length of this array is doubled, only one more comparison is made. If it is increased by four times, two more comparisons are made. We see a logarithmic relationship and thus this algorithm is said to run in logarithmic time, or have a complexity of O(lg n), where lg is shorthand for log to the base two. Wakie, wakie! Good. Earlier, I mentioned that computer science is not about computers. I guess I should put my money where my mouth is. Don Knuth is a computer scientist who means serious business. Please note the resemblance he has with Master Yoda (Knuth also has Jedi-like characteristics.) He wrote a paper titled The Complexity of Songs 1 where he talks not about the time it takes for an algorithm to run on a machine, but the amount of memory we require to sing a song (independent of the singer.) You can take a look at this paper, but you will not understand anything for the sole reason that your name is not Donald Knuth, and your name is not Rohan Sharma. So we need to find the memory we require in of the length of the song. But what do we mean by the “length” of a song?2 Is it the number of letters in the song? Well, counting the number of letters is a very accurate way to measure the size of a song, but it is extremely difficult to get an idea of the structure of the song by looking only at the letters in it. So, we shall define the length of a song as the number of words in the song. It turns out that this is a very good definition, since the sizes of words in songs do not vary much: the shortest word is 1 letter long and the longest (“supercalifragilisticexpialidocious”) consists of 34 letters. The songs that are the hardest to memorize have a complexity of O(n), where one has to explicitly memorize every single letter (e.g. Vande Mataram, The Star Spangled Banner ). The ones that are the easiest to memorize have a complexity of O(1), which means that the memory required to sing the song is independent of the length of the song. Our ancestors had very good memories. As a consequence, songs back then were very difficult to memorize. One day, they figured out that they were going to have a hard time learning so many songs. So they decided to invent a device that would help them write songs that took up less memory. This device is something every pop group exploits to date: a refrain. However, using a refrain does not alter the complexity of a song at all. This is because we are trying to find the complexity of a song independent of the person who is going to sing a song. In any reasonable song, removing the chorus would only half the length the song. A person with a cranial capacity twice that of another will find it two times easier to the song: this implies that constant factors are irrelevant. So, the entire idea of using a chorus is a failure of epic proportions. The first real breakthrough in reducing the complexity of songs was made by a Scottish farmer named O. McDonald in the early 17th century, who managed to get a complexity of √ O n. Unfortunately, an analysis of Old McDonald had a Farm is more confusing than enlightening. I shall analyse The Twelve Days of Christmas instead, as it has the same complexity.

1

http://www.cs.utexas.edu/s/arvindn/misc/knuth song complexity.pdf My good friend Arijit suggested taking an integral. However, he was oblivious to the fact that a song is a discrete distribution of certain linguistic units, which renders his suggestion absolutely meaningless. 2

2

The structure of the song looks like this: On the nth day of Christmas, my true love gave to me gifts The part “On the nth day of Christmas, my true love gave to me” is easy to when compared to memorizing the gifts and can be neglected. The length of this song for n days of Christmas is the sum of all integers from 1 to n, which simplifies to a constant times n2 plus some lower order , which is O(n2 ). Getting the memory required to learn the song is √ simply a matter of taking the inverse, which is clearly O( n). √ But a complexity of O( n) is not sufficient enough: The Twelve Days of Christmas is not the kind of song people sing during bus journeys. So what do people sing during bus journeys? n bottles of beer on the wall n bottles of beer! (You) take one down, and it around n - 1 bottles of beer on the wall! The amount of memory required to sing this song depends on the value of n, as larger numbers require larger memory. We need a storage of lg n bits. This gives a complexity of O(lg n). For a couple of centuries, everyone was pleased as they knew of the existence of a song that was extremely simple to memorize. However, thanks to the advent of modern drugs in the 1970s, there was an increase in demand for a song that was even simpler to . It was due to the genius of KC and the Sunshine Band that a song of complexity of O(1) was finally written: That’s the way Uh huh, uh huh I like it Uh huh, uh huh

3