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).

Note that there are many asymptotic upper bounds for functions, i.e. T(n) = n is both O(n²) and O(n³).

The definition of an asymptotic lower bound is the exact same as the upper bound, except that we say T(n) is Omega(f(n)) if, for sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n).

If a running time T(n) is both O(f(n)) and Omega(f(n)), then we say that it is Theta(f(n)) indicating that T(n) grows exactly like f(n) to within a constant factor.

For example, consider T(n) = pn² + qn + r.

• T(n) =< (p + q + r)n² so T(n) is O(n²,
• T(n) >= p² so T(n) is Omega(n²),
  • Therefore T(n) is Theta(n²).

1. Let f and g be two functions such that lim_n→infty f(n)/g(n) exists and is equal to some c > 0. Then f(n) = Omega(g(n)).
2. Transitivity holds for O, Omega, and Theta. E.g. if f = O(g) and g = O(h), then f = O(h).
3. Sums of functions: if f = O(h) and g = O(h), then f + g = O(h). Moreover, this extends to any finite sum of functions f_i where each f_i = O(h).
4. If g = O(f), then f + g = Theta(f). I.e. f is an asymptotically tight bound for the combined function f + g.

• Polynomials: growth determined by high-order term.
  • Let f be a polynomial of degree d in which the coefficient a_d > 0. Then f = O(n^d). Moreover, f = Omega(n^d) as well, so it follows that f = Theta(n^d).
• Logarithms: slowly growing–bounded above by polynomials.
  • For every b > 1 and every x > 0, we have log_b n = O(n^x).
  • Can translate between bases, but often base is left out because log_a n = (1/log_b a) log_b n, so log_a n = Theta(log_b n), meaning it is irrelevant when discussing bounds using asymptotic notation.
• Exponentials: of form f(n) = rⁿ for some constant base r.
  • For every r > 1 and every d > 1, we have n^d = rⁿ. That is, every exponential grows faster than every polynomial.
  • For the most part, this renders algorithms useless.

This was a nice section, also a 9 out of 10. Very readable, and I particularly like how they are getting down into the mathematical foundations a bit more now.

Our previous analysis of the G-S Stable Matching Algorithm was at a relatively high level of abstraction–finding the O(n²) bound based simply on the maximum number of iterations of the While loop. To dive deeper into analysis of the actual number of computational steps of any algorithm, we must consider the actual implementation–primarily, what data structures we will use and how they will interact. Here, we will discuss an implementation of stable matching using simply lists and arrays. First, the pros and cons of the two are weighed, and their advantages in certain situations considered (omitting from copying down here, at this point in the CSCI minor it's all ingrained pretty permanently).

Importantly, because we know the While iteration can run n² times in the worst-case, to have an implementation run in proportional time, we need each iteration to run in constant time. For simplicity, each man and woman are associated to a number from 1 to n at the outset. We use two arrays to represent the preference lists of men and women. Note the space required for this is O(n²), because each person must rank the n members of opposite sex. Now, we proceed to find a way to do the following in constant time:

1. Identify a free man (maintain set of free men as linked list; then access to first, deletions, and additions are all in constant time)
2. For man m, id the highest ranked woman to whom he hasn't proposed (single array, with one index for each man; each value initialized as “1”, then updated to always refer to index of the woman to whom he should propose next)
3. For woman w, must check if she is engaged, and if so, who her current partner is (similar to above: single array with an index for each woman; values initialized to a null symbol, and then updated to be the index of the man to whom she is engaged)
4. For woman w, must be able to see whether she prefers m or m' (at start of algorithm, create n x n array which contains a row for each woman whose position indices correspond to the ID's of each man; the values at those indices contain the numerical ranking that the woman gave to the corresponding man; then, given two men, we can access their respective rankings and compare them in constant time)

The last 2-d array is essentially the preference lists of the women, but ordered by the men's ID's themselves, not by ranking. Note that we can create this at the outset with a single pass through the women's preference lists–proportional to O(n²) in the first place. With the above structures, we implement the algorithm in O(n²) time.

I found this section very readable, a 9/10. Their use of the monospacing in reffering to data structures and values within them is incredibly helpful in understanding what they are trying to convey.