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.