Chapter 2

This section reminded me of what we learned in the CSCI 112 course at W&L. This section focused on runtime and memory allocation in terms of efficiency. It was fairly straightforward and easy to read. Reading about runtime for algorithms, it reinforced what I had learned in my previous computer science courses (big O notation). The methodology behind finding efficiency is to start by analyzing worst-case run times. For example, in the stable matching problem, we should consider the search space (which, in this case, is huge- n! possible perfect matchings).

This section was a lot more difficult to understand than any of the previous sections. On a scale of 1-10, this section was about a 6 for me in regards to how readable it was. This section mainly covered upper and lower bounds for some function, f(n) where T(n) is the worst-case. For upper bounds, T(n) is O(f(n)). For lower bounds, T(n) = Ω¹⁾). If T(n) is in between these two values, than it is considered Θ(f(n))) which means that f(n) is an asymptotically tight bound for T(n).

As I was unable to attend the last class due to illness, this discussion very much confused me. The following discussion, however, did make some sense. These functions have certain properties. Two of these properties includes the transitive property and the sums of functions. This makes sense as these properties apply to any mathematical function, and should therefore apply to any algorithm. Furthermore, this section discussed three main types of notations: polynomials, logarithms, and exponentials. Working with various Big O notations in CSCI 112 will help to remember these various notations, but it may be more difficult to try and remember the asymptotic bounds.