Chapter 2

Analyzing algorithms involves thinking about how their resource requirements—the amount of time and space they use—will vary with increasing input size, N. This input size is used to describe efficiency in terms of Big-O notation (to be discussed later).

We want algorithms that run quickly. In other words, they are efficient with respect to time. But, it is important that the algorithms be efficient in their use of other resources—in particular, memory—as well. Efficiency in terms of running time is measured with respect to the size of the input, N. The idea is to look for a bound on the largest possible running time the algorithm could have over all inputs of a given size N, and see how it scales with N—this approach is called the worst-case analysis. The alternative to this approach is called the average-time analysis. It studies the performance of an algorithm averaged over “random” instances, but can be difficult and often impractical to implement.

Revisiting our example of the Stable Matching Problem, we can see that the use of brute-force search (i.e., try all possibilities and see if any of them works) over the search space of possible solutions is extremely inefficient in terms of runtime. There are n! possible perfect matchings between n men and n women. The brute-force algorithm typically takes 2^N time or worse for an input of size N. In contrast, the Gale-Shapley algorithm solves this problem in O(N^2) runtime.

We can then say that an algorithm is efficient if it has a polynomial running time. It should be noted, however, that problems for which polynomial-time algorithms exist almost invariably turn out to have algorithms with running times (almost) proportional to polynomials like n, n logn, n^2, or n^3. The use of polynomial-time bounds is only an abstraction of practical situations. Hence, with our definition of efficiency, it is possible to express the notion that there is no efficient algorithm for a particular problem.

When we provide a bound on the running time of an algorithm, we will generally be counting the number of pseudo-code steps that are executed. In this context, one step will consist of 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. We want to express the growth rate of running times and other functions in a way that is insensitive to constant factors and low-order terms. For example, for a running time like 1.62n^2 + 12n + 6, we want to say that the algorithm grows like n^2.

Let T(n) be the worst-case running of an algorithm on an input size of n. Given another function f(n), we say that T(n) is O(f(n)) if there exist constants c > 0 and n’ ≥ 0 such that for all n ≥ n’, it is the case that T(n) ≤ c·f(n). In this case, T is asymptotically upper-bounded by f. It is important to note that O(x) only expresses an upper bound, and not the rate of growth, of the function. Therefore, something that is O(n^2) is, by definition, also O(n^3). Ideally, we want the lowest upper bound to best analyze and compare the running times of algorithms.

We want to express the notion that for arbitrarily large input sizes n, the function T(n) is at least a constant multiple of some function f(n). We say that T(n) is Ω(f(n)) if there exist constants ε > 0 and n' ≥ 0 so that for all n ≥ n', it is the case that T(n) ≥ ε·f(n). We refer to T in this case as being asymptotically lower-bounded by f.

This definition works just like O(x), except that we are bounding the function T(n) from below instead of from above.

If a function T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n)). In other words, f(n) is an asymptotically tight bound for T(n). Such bounds can be found by closing the gaps between upper bounds and lower bounds.

When designing an algorithm, one has to think about how the data will be represented and manipulated, so as to bound the number of computational steps it takes.

In the Stable Matching Problem, each man and each woman has a ranking of all members of the opposite gender. The very first question we need to discuss is how such a ranking will be represented. Further, the algorithm maintains a matching and will need to know at each step which men and women are free, and who is matched with whom. In order to implement the algorithm, we need to decide which data structures we will use for all these things.

We can use arrays and linked lists to implement the Stable Matching algorithm. If we actually want to implement the G-S algorithm so that it runs in time proportional to n^2, we need to be able to implement each iteration in constant time. We can define an array indexed by all men or all women (by ordering the men or women–e.g. alphabetically). We need to have a preference list for each man and for each woman. To do this we will have two arrays, one for women’s preference lists and one for the men’s preference lists. To select a free man, we will maintain the set of free men as a linked list. We need to identify the highest-ranked woman to whom a man m has not yet proposed. To do this we will need to maintain an extra array Next that indicates for each man m the position of the next woman he will propose to on his list. We need to be able to identify the man m’ that w is engaged to (if there is such a man). We can do this by maintaining an array Current of length n, where Current[w] is the woman w’s current partner m’.

We would like to decide in O(1) time if woman w prefers m or m’. Keeping the women’s preferences in an array WomanPref, analogous to the one we used for men, does not work, as we would need to walk through w’s list one by one, taking O(n) time to find m and m’ on the list. At the start of the algorithm, we create an n x n array Ranking, where Ranking[w, m] contains the rank of man m in the sorted order of w’s preferences. By a single pass through w’s preference list, we can create this array in linear time for each woman, for a total initial time investment proportional to n^2. Then, to decide which of m or m’ is preferred by w, we simply compare the values Ranking[w, m] and Ranking[w, m’]. These data structures allow us to implement the Gale-Shapley algorithm in O(n^2) time.

Personally, I found it really cool how we used the restriction of having O(n^2) running time on the G-S algorithm to reverse-engineer the implementation for the algorithm and then decide what data structures to use. One thing I found particularly interesting was the use of the n x n array to initialize and keep track of the women's preference lists, as opposed to just using an array of size n, to reduce this step from O(n) to O(1) in order to keep the run time O(n^2) overall.

I read this section before covering it in class, and it didn't really make much sense at the time. Having heard class discussions on why certain data structures are best for the algorithm, I went back to read this section again–and it made much more sense.

There are several running time bounds that appear over and over again in algorithm analysis. A few of these are given below:

An algorithm that runs in O(n) time has a running time that is at most a constant factor times the size of the input. Such algorithms often involve processing the input in a single pass, and performing constant time operations on each item of the input. Examples of such algorithms include computing the maximum of n numbers, and merging two sorted lists.

O(n log n) is the running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear time. One of the most well known problems that can be solved in O(n log n) time is sorting–more specifically, the efficient sorting algorithms. One such sorting algorithm is Mergesort, which divides the set of input numbers into two equal-sized pieces, sorts each half recursively, and then merges the two sorted halves into a single sorted output list.

Quadratic time naturally arises from a pair of nested loops: An algorithm consists of a loop with O(n) iterations, and each iteration of the loop launches an internal loop that takes O(n) time. Multiplying these two factors of n together gives the running time of O(n^2).

The less efficient sorting algorithms, e.g. insertion sort, also fall under this category of running time.

More elaborate sets of nested loops often lead to algorithms that run in O(n^3) time. For example, consider a problem involving nested for-loops that iterate over the input. Each level of the loop will be O(n) running time, making the for-loops O(n^2). If, inside the inner nest for-loop, there are statements that run in linear time, for example indexing a linked list, the entire algorithm will end up being O(n^3).

We obtain a running time of O(n^k) for any constant k when we search over all subsets of size k. An example of problems that run in O(n^k) time is the Independent Set problem, which can be solved by the algorithm (from the textbook) below:

For each subset S of k nodes
    Check whether S constitutes an independent set 
    If S is an independent set then
        Stop and declare success Endif
Endfor
If no k-node independent set was found then
    Declare failure 
Endif

O(n!) is a running time that belongs to the set of running times beyond polynomial time. The function n! arises in problems where the search space consists of all ways to arrange n items in order. A basic problem in this genre is the Traveling Salesman Problem: given a set of n cities, with distances between all pairs, what is the shortest tour that visits all cities? We can assume that the salesman starts and ends at the first city, so the crux of the problem is the implicit search over all orders of the remaining n-1 cities, leading to a size (n-1)! search space.

This section was pretty intuitive. Sections 2.4.1 through 2.4.4 were basically a recap of things we learned in CSCI-112 (or other Computer Science classes).

However, sections 2.4.5 and 2.4.6 were less intuitive for me. Probably due to the nature of the problems involved. It took me several attempts at reading and a few online searched to fully understand what is happening in the Independent Set problem. The Traveling Salesman Problem was more intuitive (it is basically just about permutations), but I had trouble trying to come up with practical problems in every day Computer Science that would have a running time of O(n!).