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’s 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, especially for algorithms we’ve seen in earlier courses. 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 prove correct. In particular, correctness proofs usually involve induction. We like induction. Induction is our friend.

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’s 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 we 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.”$ ...