Chapter 2: Basics of Algorithm Analysis

When considering computational algorithms, two crucial aspects are the algorithm's usage of physical memory space, and its run-time. In many situations we will find that a balance must be struck between the two.

This section focuses on the running time side of things. Obviously, given any problem, it is critical to find as efficient an algorithm as possible for solving it. In working toward an objective, mathematically significant definition for efficiency, we see that the primary focus is considering the worst case scenario of algorithm input and run-time. This is because the best case is often trivial and illuminates nothing, and the “average case,” although it can yield insight in many cases, is a difficult thing to define in abstraction, and therefore over-complicates things.

Firstly, for a given algorithm to be useful, we would expect it to perform better than a brute force search, or the consideration of every possible situation (in terms of the G-S stable matching algorithm, this would entail checking every single perfect matching combination). So we land at the following definition:

• An algorithm is efficient if it has a polynomial running time, meaning:
  • there exist constants c > 0 and d > 0 such that for sufficiently large input instances N, the running time is bounded by cN^d primitive computational steps.

Put simply, if the input size were to increase by a constant factor (e.g. double), then the running time should also only decrease by a constant factor. Examples of polynomial run time bounds are n, nlog₂n, n², and n³. Fortunately, in practice it turns out that if an algorithm exists with an impractically high order polynomial bound, such as n¹⁰⁰, then it tends to indicate that a lower order bound indeed also exists.

One of the primary benefits of the above specific definition is its objectivity and therefore exact application from abstraction to implementation. Additionally, it is negatable.

I would rank this section a 9, it was very easy to read and very much complemented the class discussion.

This