Chapter 2: Basics of Algorithm Analysis

Several factors are key in the design of algorithms, including understanding the discrete nature of many problems as well as addressing the efficiency and space of an algorithm. The text gives one definition of efficiency: “An algorithm is efficient if, when implemented, it runs quickly on real input instances.” Unfortunately, this definition fails to consider where and how well the algorithm is implemented.

To be more specific, we can argue that an algorithm is efficient if it, at the bare minimum, performs in the worst case better than would a brute-force search. To narrow the definition even further, we could classify an 'efficient algorithm' as one with a polynomial running time, meaning its running time is bounded by cN^d where c and d are constants > 0 and every input instance is size N. I found it beneficial to learn more about what exactly makes an algorithm efficient and I would rate this section a 10 for its ability to be clearly understood, since concepts were explained very straightforwardly.

For the purposes of simplicity and clarity, classifying running times should be done in terms of constant factors; for example instead of calculating a run time as an² + bn + c, we would consider this run time to be simply n². Assume T(n) is the worst-case run time for an algorithm with n referring to the size of the input. Let f(n) refer to a function. T is asymptotically upper-bounded by f and T(n) is O(f(n)) if:

• there exists a constant c > 0
• there exists and a constant n₀ ≥ 0 such that all n ≥ n₀, and
• T(n) ≤ c • f(n).

Suppose T(n) ≥ d • f(n), for a fixed constant d > 0; then T is asymptotically lower-bounded by f and Ω(f(n)). Finally, if T(n) is both O(f(n)) and Ω(f(n)), then T(n) is considered asymptotically tight bound for T(n) and T(n) is θ(f(n)).

The growth rates O, Ω, and θ share some basic properties:

• transitivity: if a function f is asymptotically upper-bounded by a function g and g is asymptotically upper-bounded by a function h, then f is asymptotically upper-bounded by h.
• if f = θ(g) and g = θ(h) then f = θ(h)
• if f = O(h) and g = O(h) then f + g = O(h)
• if g = O(h) then f + g
• if g = O(f) then f + g = θ(f)

Logarithms, polynomials, and exponential functions are various ways to classify running time, with logarithms growing the slowest and exponentials growing the fastest. It was interesting to learn more deeply about run time order, for it has been frequently discussed throughout many of my courses. This section provided a deeper understanding on the variety of run time functions. I would have liked more information on how algorithms' run times are calculated. The readability of this section was around a 7, because the various variables, rules, and terms were somewhat complicated to keep straight.

Deciding how data will be represented in an algorithm is critical in the calculation of running time. In the Gale-Shapley algorithm, the only data structures needed are lists and arrays. Using arrays has several benefits, including constant-time access for the i^th item, linear running time for searching if an item is in the array, and O(logn) for binary search of a sorted array. In contrast, a list will benefit us when we are dealing with a group of elements that are changing, since adding and deleting items is more efficient with a list than with an array.

In order to attain a preferable run time for the Gale-Shapley algorithm, we must choose data structures to model our data which will be most beneficial for their use. For example, we will store the preference lists of the men and the preference lists for the women in arrays, since this data structure is ideal for accessing the i^th item. While some data structure decisions seem clear, such as using a linked list to denote the free men, since items will be added and removed from this structure, but other choices are more difficult. Maintaining a woman's preferences can be done most efficiently by using an n x n array which stores the rank of a man for a particular woman. The most important result of this is allowing constant-time for this step, and therefore establishing the run-time for the entire algorithm as O(n²).

I did not find this section as easy to follow as our discussion in class about the same decisions. If we had not worked through these questions prior to this reading I would have had a very hard time understanding their logic, since it was weakly justified. I rate this section a 5 for readability. I would also have liked a more in-depth explanation of the method to ensure O(n²) running time as opposed to O(n³), which we discussed in class.

As we learned earlier, when creating algorithms a goal is to have a more efficient running time than a brute-force algorithm would have. There are several common run times that appear frequently in algorithms, including linear time, nlogn time, quadratic time, cubic time, and n^k. Linear time means the running time is at most C • n, where C is a constant and n is the input size. Some examples of algorithms with linear running time is one which computes the maximum of n numbers and merging two sorted lists. In terms of algorithms that have O(nlogn), this can be used to describe algorithms which split their inputs into two pieces and solve each half recursively, then combine each solution in linear time. Most commonly, this procedure is seen in the merge sort algorithm. One example of an algorithm with quadratic time is one with nested loops, such as an algorithm which iterates over items of two arrays, performing a constant operation inside the loops. For cubic time, algorithms which perform more complex operations inside nested loops typically follow this pattern. An example of O(n^k) running time is one which finds independent sets in a graph.

There are some running times that are worse than polynomial running time, including 2ⁿ and n!. These functions grow faster than polynomials and therefore are not ideal running times for algorithms. Algorithms which search through all subsets have a running time of 2ⁿ. Algorithms which pair n items with n items or those which consider the ways to arrange n items in order have a running time of n!, which is worse than 2ⁿ. In addition, some algorithms run in logn time, which is slightly better than linear time.