Chapter 2: Basics of Algorithm Analysis

This section tries to formulate a definition for efficiency. It outlines that we cannot simply define efficiency as speed, because even bad algorithms run quickly on fast computers or when they are run with only small test cases. When looking at efficiency we look at the worst-case scenario as best-case is not particularly realistic and average-case analysis does not really help us look at how the algorithm works and instead looks at how the input is generated. If we were to attempt to work through a problem using just “brute-force” we would end up with insanely poor run times. The section also discussed polynomial run times which means that as the input size of an algorithm increases by a constant factor, the run time will also slow by a constant factor. When we define efficiency using polynomial run times, we create a definition that is negatable. This way we are able to say that there is not an efficient algorithm for a problem.

The motivation behind this section’s discussion is a desire to create algorithms that are both correct and efficient. However, in order to properly determine what is efficient we have to define efficiency in a way that we will be able to prove. If we cannot prove efficiency then we cannot prove that we have created a working, useful algorithm.

There were no specific algorithms discussed in this section.

I am still a little confused about the two constants, c and d, and how they interplay with each other and how they relate to run time.

After reading this, the relationship between the input size and the algorithm speed became more clear and concrete. It also provided the reasons why we should be concerned with run time and how run times can explode if we are not careful.

I would give this section a 7 for interest and readability as it was once again straightforward, but not as interesting as the section on the actual algorithms.

Bounds of runtime functions are the “worst-case” scenarios that an algorithms runtime is bounded by. A bound can be an upper bound, which is denoted O(f(n)), a lower bound, which is denoted Ω(F(n)), or a tight bound, which is denoted Θ(f(n)). An upper bound occurs when the algorithm’s function is bounded above by a multiple of f(n). A lower bound occurs when the algorithm’s function is less greater than f(n) times some constant. Finally a tight bound occurs when the upper bound and lower bound are the same. The section traced through some examples that solidified these definitions. Asymptotic bounds have many properties including transitivity and additivity. Transitivity means that if f = O(g) and g = O(h), then f = O(h). Another properties of bounds is that if f and g are two functions such that g = O(f) then f + g = Θ(f). Finally the section discussed polynomial (n raised to a power), logarithmic, and exponential (a constant raised to a power of n) bounds. It outlined how to develop these different algorithms as well as needed notation and conversions. The exponents do not need to be whole numbers and the bases of logarithmic functions are not important. These three types of bounds provide solid benchmarks in ranges of functions.

The motivation for looking at asymptotic bounds is to have a concrete way of describing the worst-case scenario. It allows us to narrow our prediction of how quickly an algorithm will run and gives us a close range as opposed to a bunch of possibilities. We can also see how the runtimes of programs will be affected by adding different algorithms together.

This section was a lot of notation and it is a little confusing. I think going through some real life examples will help to clarify as thinking about it abstractly is difficult.

I would give this section an 7 out of 10 as it was a little dry to read and was just a lot of notation.

The run time of an algorithm can be greatly affected by the data structures used within the algorithm and the book strives to show how we can find data structures that make algorithms efficient to run and easy to implement. The section then goes in depth on the proper data structures to use to achieve a run time of O(n^2) while running the Stable Matching Algorithm. O(n^2) can be achieved by using several arrays, a linked list, and implementing an array for women's preferences outside of the while loop.

The motivations are to create an algorithm that is both easy to create and runs efficiently regardless of the input size.

This was pretty straightforward although I felt that it was more confusing to try and read about it as opposed to when we discussed it in class.

I would give the section a 6 out of 10. Since we had discussed this at length in class already, the section was not super helpful and was a little confusing at times.

The best way to approach a new problem is to think about both the bound on the running time you want to achieve and the bound on the search space. Then it helps to be able to recognize the common runtimes and the algorithms they are generally associated with. Linear time, O(n), occurs when you process input in one fell swoop, so that the run time can only be a constant factor of the size n of the input. O(n logn) occurs when an algorithm has to “split the input into two pieces, solves each piece recursively, and then combines the two solutions in linear time” (pg 50). Quadratic time, O(n^2), is generally associated with nested loops when each loop runs in O(n) time. Cubic time, O(n^3), similarly occurs when there are more nested loops. O(n^k) time is found when an algorithm must search over all subsets of size k where k is a constant. Finally, O(2^n) and O(n!) were discussed as two very fast growing runtimes that are generally avoided if possible. 2^n is a result of searches of all subsets and n! is a result of a search space that requires the algorithm to match up n items with n different items in every possible way or arrange these items in every possible order. There are also sublinear run times, such as O(logn) which can occur if the search region shrinks during each pass of a loop, as in the binary search algorithm.

The section discussed the Stable Matching Problem, binary search, Independent set, and several other 'nameless' algorithms as examples for each run time.

Most of this discussion was a much-needed recap of what I had learned in 112 so I feel pretty good about most of the section discussed.

I would give this section a 8/10 because it was incredibly helpful and created a place where I can easily reference needed runtimes.

The priority queue is a data structure that organizes items in an array-like structure where each item has a priority value. When we remove items from the list we take the one with the highest priority first. However, sorting algorithms involved with priority queues run in O(n^2) time and we would like to be able to have O(n logn) time. So we implement a priority queue with a heap. The heap is a data structure similar to a binary search tree. The heap allows us to create a sorting algorithm in O(n logn) time. It uses two algorithms, Heapify-Up and Heapify-Down, to move values through the heap so that it stays in heap-order. Heap-order is when each child is greater than or equal to its parent. The algorithms used in this section are Heapify-up (page 61) and Heapify-down (page 63). Both algorithms are O(n logn) and allow us to run a sorting algorithm in O(n logn) time. I am still a little confused on why we just don’t call the heap a priority heap. The distinction between a type of heap and then a priority implemented with a heap. I would give this section an 8/10. It was interesting and was very easy to follow. It also helped reinforce the ideas that we covered in class.