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, n log₂ 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.

To move further into the discussion of algorithm running times, a few clarifications and simplifications are in order. First, for the most part we will be considering steps in our pseudo-code algorithms to be anything such as assigning a value to a variable, looking up an entry in an array, following a pointer, or performing an arithmetic operation on a fixed size integer. Additionally, because constants and lower order terms become inconsequential at larger inputs, we have an impetus for abstraction to highest-order polynomial upper bounds.

Given a function T(n), we say that T(n) is O(f(n)) (read T(n) is order f(n)) if, for sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n). Mathematically put, that is if there exist constants c > 0 and n₀ > 0 such that for all n > n₀, we have T(n) =< c * f(n).