Chapter 2

The first attempt to describe efficiency is that “an algorithm is efficient if, when implemented, it runs quickly on real input instances.” This is good, but it fails to address on what type of machine the algorithm is being run, how well it runs, and the scalability it possesses.

We can consider worst-case runtimes and brute force methods on the way to a better definition of efficiency. It is important to use a worst-case run time to compare performance of algorithms because using the alluring average-case ignites a debate over how to arrive at the random values to input into a function. A good benchmark with which to compare an algorithm's worst-case run time is the run time of its brute-force method, which traverses the entire search space for a solution. These two components lead us to the next definition of efficiency, which is: “an algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search.” A qualm we may have with this is how to define “qualitatively better running time.”

The use of polynomial time gives us the ability to evaluate algorithms using quantitative analysis. The desirable scaling property of algorithms states that there exists constants c > 0 and d > 0 whose running time is bounded by CN^d, thus the algorithm slows down by a constant factor of 2^d when N increases to 2N and this yields a third definition of efficiency: “an algorithm is efficient if it has a polynomial running time.” One last, unexpected result of this definition is that we now have a definition that can be tested quantitatively and proven or disproven.

An algorithm's worst-case running time can be tested quantitatively by computing its algorithmic upper and lower bounds. To prove that an algorithm has an asymptotic upper bound of n² we can imagine one whose worst-case running time T(n) is f(n) = pn²+qn+r. We can prove that this function is O(n²) with the inequality T(n)=pn²+qn+r < = p²+q²+r²=(p+q+r)n² thus T(n) < = cn² where c = p+q+r.

An algorithm's asymptotic lower bound can be proven in a similar fashion. First, a note about notation: asymptotic lower bounds are conventionally represented by an omega, which can not be represented in this markup, so <OMEGA> will be its stand-in. We can prove that an algorithm whose worst-case running time T(n) is <OMEGA>(n²) when it has a worst-case running time modeled by the function T(n)=pn²+qn+r with the inequality T(n)=pn²+qn+r > = pn².

Additionally, we can use both of these components to arrive at an asymptotically tight bound. When T(n) = O(f(n)) = <OMEGA>(f(n)), it is safe to say that T(n) = <THETA>(f(n)). Another way to compute asymptotically tight bounds is to take the limit of f(n)/g(n) as n goes to infinity.

Finally, asymptotic growth rates have properties of transitivity (if f is bounded by g and g is bounded by h, f is bounded by h so long as f and g are both bounded in the same direction) and the ability to be summed (if f is upper bounded by h and g is upper bounded by h, f+g is upper bounded by h).

Analytically, we have found that the Gale-Shapley stable matching algorithm can run in O(n²) time. This is the result of the loop that drives the progress of the algorithm running in O(n²) time, which means that each step within the loop must run in constant time. Our task, then, is to determine which data structures to implement in order to support this constant time execution of steps within the loop.

The first step in deciding which data structures to implement is identifying what will be happening in each instruction within the loop: 1) choosing a free man; 2) for a man m, find the highest-ranked woman to whom he has not yet proposed; 3) for a woman w, find if she is engaged and if so, identify her current partner; 4) find which man, m or m' that a woman w prefers.

For step 1, the algorithm will be choosing a single man in no specific order. If he becomes engaged, he will be deleted from the list and a man m' will be added to the list if m just replaced him as woman w's engagement. Since the size of this list will be continually changing, it would be better to implement it as a linked list, since items can be added and removed to and from the front of a linked list in constant time.

Step 2 requires the tracking of the position of the next woman in a man m's preference list. All of these for each man will be initialized at 1 and every time m needs to propose to a woman, he will choose w = [ManPref[m, Next[m]] and Next[m] will be incremented, regardless of success. This is better suited to the strengths of an array, since it will hold the same amount of data throughout the running of the algorithm and the array affords constant time access to values at any position within.

The third step inside the loop is concerned with deciding whether a woman is engaged and if so, identifying the partner to whom she is engaged. The value Current[w] is m' when w is engaged to m' and when she is not engaged the value will be null. It is interesting which is why this step is excellent to implement using an array. An array holds the same amount of data throughout the running of the algorithm and supports constant-time indexing and replacements.

The last thing that the algorithm must do in constant time is compare a woman w's rankings of her current man m and a new proposal m'. Since the length of the preference list is certain and the algorithm needs constant-time access of any position in order to keep overall running time O(n²), an array should be used here. A two-dimensional array is needed, since each of n women will have preference lists of length n. This structure will take O(n²) time to implement at startup, but since that will take place outside of the loop, it only affects the constant coefficient running time of the algorithm.

I found this section easy to read and I appreciated how it began with a review of the unique characteristics of each data type and then discussed the steps that occurred inside the loop, including details that ushered the reader towards the implementation of one data structure or the other. The final section with rigorous explanations of why one data type was preferred over the other for each step helped show what to look for in components of other algorithms when trying to decide which data structures to implement.

The first common running time treated in this section is O(n) running time. This is sometimes described as a “Linear” running time because the running increases linearly, or at the same rate as the input size. Common causes of a linear running time are loops that iterate through every item in an input or algorithms that apply a constant number of processes to each item in an input. Some examples of linear running times include finding the maximum value of an unsorted array and merging two sorted lists.

Another common run time is O(n log n). This is the run time of any algorithm that cuts an input in half, recursively solves each half and recombines them. An example of an algorithm that works like this is mergesort.

Quadratic and Cubic times are also seen a lot, due to the fact that they are the product of a loop within a loop or a loop within a loop within a loop, respectively. Quadratic time can also arise from a situation where an algorithm must perform a search over all input items and then expend constant time operating on each pair. One algorithm that uses an O(n²) running time is the Closest-pair problem, which searches through a set of pairs using a nested loop and calculates the distance between each one, tracking the minimum as it runs and resetting if necessary. Cubic time shows up in the algorithm that searches n sets to see if any are disjoint. It runs in O(n³) because it uses a nested for loop to pick pairs of sets, then a for loop inside of that to compare each item in each set for equality. In worst case, it compares every item in each of n sets, making O(n³) comparisons.

Some algorithms can run in the worst case at times that are worse than polynomial. These include running time such as exponentials and factorial growth rates. Exponentials arise in algorithms that consider all subsets, such as Independent Set, which is a computationally hard problem that requires an algorithm to find the independent set of maximum size. Factorials grow even faster than exponentials, and that class of running times includes problems that involve matching n items with n other items or arranging n items in order.

Sublinear time is a special treat that arises when an input can be “queried,” which means that there is information that can be used to help the algorithm navigate the input intelligently rather than visiting each input item individually. This is the case with the O(log n) algorithm which is able to throw away half of the input without even visiting it based on the value of the item that it visits, which will be in the middle of the remaining items.

This chapter was very straightforward and easy to read due to it discussion of running times, which I have studied before.

Statement 2.11 from the book says that “a sequence of O(n) priority queue operations can be used to sort a set of n numbers”. This is because the set of numbers can be inserted into it with their value as their priority and then extracted in order of priority, resulting in their being in sorted order. I wondered when reading this, then, why we can not come up with a linear sort algorithm? I know I must be missing something but why is this not a linear sort?

Regardless, we will use a heap to implement our priority queue. It helps to visualize a heap as a balanced binary tree with a root node and each node having two or fewer child nodes. The heap will be represented in an array with an object at position i, its left child at 2i and its right child at 2i+1. Importantly, the value at any child node can not be less than the object at its own parent node.

Maintaining the heap order in an array during additions and deletions requires special algorithms that rearrange the nodes and allow for insertion and deletion in O(log n) time. First, to add an item to the heap, it is inserted into position n + 1 (for a heap of size n) and then Heapify-up is called. Heapify-up checks whether the recently inserted value is less than the value of it parent node and if so, it swaps the two and recursively calls itself. This maintains heap order by pushing lower values towards the top of the array. To delete an item in a heap and maintain heap order, the item at position n is placed in the array where the item to be deleted had been, and then Heapify-down is called. As one would expect, Heapify-down works in the opposite direction of Heapify-up by comparing a parent to its children and swapping the parent with the lower child if possible. This algorithm also calls itself recursively until heap order has been restored.

Some important running times to note when implementing priority queues with heaps:

• StartHeap(N) initializes an array of size N in O(N) time

• Insert(H, v) inserts v into heap H using Heapify-up, for a heap of size n this takes O(n) time

• FindMin(H) Identifies the minimum element which is the root node using O(k) time

• Delete(H, i) deletes the element at position i using Heapify-down for O(log n) time

• ExtractMin(H) combines FindMin(H) and Delete(H, i) to delete the min in O(log n) time