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.