Analyzing Algorithms

It’s not enough just to write down an algorithm and say, “Behold!” We must also convince our audience (and ourselves!) that the algorithm actually does what it’s supposed to do and that it does so efficiently.

Correctness

In some application settings, it is acceptable for programs to behave correctly most of the time, on all “reasonable” inputs. Not in this course: we require algorithms that are always correct, for all possible inputs. Moreover, we must prove that our algorithms are correct; trusting our instincts, or trying a few test cases, isn’t good enough. Sometimes correctness is truly obvious. On the other hand, “obvious” is all too often a synonym for “wrong.” Most of the algorithms we discuss in this course require real work to be proven correct. In particular, correctness proofs usually involve induction. Induction is an incredibly useful method.

Of course, before we can formally prove that our algorithm does what it’s supposed to do, we have to formally describe what it’s supposed to do.

Running time

The most common way of ranking different algorithms for the same problem is by how quickly they run. Ideally, we want the fastest possible algorithm for any particular problem. In many application settings, it is acceptable for programs to run efficiently most of the time on all “reasonable” inputs. Not in this course—we require algorithms that always run efficiently, even in the worst case.

What’s important here is how the singing time changes as $n$ grows. Singing $BottlesOfBeer(2n)$ requires about twice as much time as singing $BottlesOfBeer(n)$, no matter what technology is being used. This is reflected in the asymptotic singing time $Θ(n)$.

We can measure time by counting how many times the algorithm executes a certain instruction or reaches a certain milestone in the “code.” For example, we might notice that the word “beer” is sung three times in every verse of “Bottles of Beer,” so the number of times you sing “beer” is a good indication of the total singing time. For this question, we can give an exact answer: $BottlesOfBeer(n)$ mentions beer exactly $3n + 3$ times.

Incidentally, there are lots of songs with quadratic singing time. This one is probably familiar to most English speakers:

$\underline{NDaysOfChristmas(gifts[2 .. n]):} \\ \hspace{0.4cm} for\space i←n \\ \hspace{1cm} Sing\space “On\space the\space ith\space day\space of\space Christmas,\space my\space true\space love\space gave\space to\space me” \\ \hspace{1cm} for\space j ← i\space down\space to\space 2 \\ \hspace{1.7cm} Sing\space “j\space gifts[j],” \\ \hspace{1cm} if\space i > 1 \\ \hspace{1.7cm} Sing\space “and” \\ \hspace{1cm} Sing\space “a\space partridge\space in\space a\space pear\space tree.”$

Explanation

• Line 2: We set up a loop that will iterate over the range of numbers from n to 2 (inclusive) in reverse order.

• Lines 4–5: We print the gifts for each day of Christmas. The end="" argument to the print function is used to prevent it from printing a newline character after each gift.

• Line 25: We set the variable n to the length of the gifts list minus 1, which is the number of days of Christmas to print.

The input to $NDaysOfChristmas$ is a list of $n − 1$ gifts, represented here as an array. It’s quite easy to show that the singing time is $Θ(n^2$); in particular, the singer mentions the name of a gift $\sum_{i=1}^{n} i = n(n + 1)/2$ times (counting the partridge in the pear tree). It’s also easy to see that during the first n days of Christmas, “my true love gave to me exactly $\sum_{i=1}^{n} \sum_{j=1}^{i} j = n(n + 1)(n + 2)/6 = Θ(n^3)$ gifts.”

Other quadratic-time songs include “Old MacDonald Had a Farm,” “There Was an Old Lady Who Swallowed a Fly,” “Hole in the Bottom of the Sea,” “Green Grow the Rushes O,” “The Rattlin’ Bog,” “The Court Of King Caractacus,” “The Barley-Mow,” “If I Were Not Upon the Stage,” “Star Trekkin’,” “Ist das nicht ein Schnitzelbank?”,22“Il Pulcino Pio,” “Minkurinn í hænsnakofanum,” “Echad Mi Yodea,” and “ To $\kappa o\kappa o\varrho \acute{}\alpha \kappa \iota$.” For more examples, consult your favorite preschooler.

$\underline{Alouette(lapart[1 .. n]):} \\ \hspace{0.4cm} \text{Chantez}\space «\space Alouette,\space gentille\space alouette,\space alouette,\space je\space te\space plumerai.\space » \\ \hspace{0.45cm} \text{pour tout i de 1 à n} \\ \hspace{1cm} \text{Chantez } «\space Je\space te\space plumerai\space lapart[i].\space Je\space te\space plumerai\space lapart[i].\space » \\ \hspace{1cm} \text{pour tout j de i à 1} 〈〈à rebours〉〉 \\ \hspace{1.7cm} \text{Chantez } «\space Et\space lapart[ j] !\space Et\space lapart[ j] !\space » \\ \hspace{1cm} \text{Chantez } «\space Alouette!\space Alouette!\space Aaaaaa. . . \space» \\ \hspace{1cm} \text{Chantez } «\space . . . alouette,\space gentille\space allouette,\space alouette,\space je\space te\space plumerai.\space »$

Explanation

• Line 1: We define a function called Alouette that takes in two parameters: lapart, which is a list of strings representing the different parts of a bird’s body, and n, which is the length of the lapart list.

• Lines 3–7: We loop through the lapart list and print out each line of the song. For each part of the bird’s body in lapart, the code prints out “Je te plumerai [part of the body].” Then, it loops backwards through the lapart list (starting from the current index i and going down to 0) and prints out "Et [part of the body] ! " for each previous part of the bird’s body. Finally, it prints out "Alouette! Alouette! Aaaaaa. . . " at the end of each verse.

Analysis of algorithmic running times

A few songs have even more bizarre singing times. A fairly modern example is “The Telnet Song” by Guy Steele, which actually takes $Θ(2n)$ time to sing the first $n$ verses; Steele recommended $n = 4$. Finally, there are some songs that never end.

Except for “The Telnet Song”, all of these songs are most naturally expressed as a small set of nested loops, so their running singing times can be computed using nested summations. The running time of a recursive algorithm is more easily expressed as a recurrence. For example, the peasant multiplication algorithm can be expressed recursively as follows:

$$x.y = \begin{cases} 0& \text{ if } x=0 \\ [x/2].(y+y)& \text{ if $x$ is even} \\ [x/2].(y+y)+y& \text{ if $x$ is odd } \end{cases}$$

Let $T(x, y)$ denote the number of parity, addition, and mediation operations required to compute $x · y$. This function satisfies the recursive inequality $T(x,y)≤T(⌊x/2⌋,2y)+2$ with base case $T(0,y)=0$. Techniques described in the next chapter imply the upper bound $T(x, y) = O(\log x)$.

Sometimes, the running time of an algorithm depends on a particular implementation of some underlying data structure of subroutine. For example, the Huntington-Hill apportionment algorithm ApportionCongress runs in $O(N + RI + (R − n)E)$ time, where $N$ denotes the running time of NewPriority- Queue, $I$ denotes the running time of Insert, and $E$ denotes the running time of ExtractMax. Under the reasonable assumption that $R ≥ 2n$ (on average, each state gets at least two representatives), we can simplify this bound to $O(N + R(I + E))$. The precise running time depends on the implementation of the underlying priority queue. The Census Bureau implements the priority queue as an unsorted array, which gives us $N = I = Θ(1)$ and $E = Θ(n)$, so the Census Bureau’s implementation of ApportionCongress runs in $O(Rn)$ time. However, if we implement the priority queue as a binary heap or a heap-ordered array, we have $N = Θ(1)$ and $I = E = O(\log n)$, so the overall algorithm runs in $O(R\log n)$ time.

Finally, sometimes we are interested in computational resources other than time, such as space, the number of coin flips, the number of cache or page faults, the number of inter-process messages, or “the number of gifts my true love gave to me.” These resources can be analyzed using the same techniques used to analyze running time. For example, lattice multiplication of two $n$-digit numbers requires $O(n^2)$ space if we write down all the partial products before adding them but only $O(n)$ space if we add them on the fly.