This is an old revision of the document!
Table of Contents
Chapter 2
Section 1: Computational Tractability
The first major question that needs to be answered in discussing algorithms is how to define what an efficient algorithm is. At first, it can be defined as an algorithm that, when implemented, runs quickly on real input instances. While this definition does highlight an important characteristic of an efficient algorithm, it does not fully encapsulate what it means to be efficient. The first missing piece of information in this definition is where/how well an algorithm is implemented. If an algorithm is run on a very fast processor even if it is poorly designed, it may still run quickly. Oppositely, a good algorithm may still run slowly if it is poorly implemented. Another uncertainty in this definition is what a “real” input instance is, as there is no bound as to what this defines. A final issue with this definition is that it doesn't discuss the scalability of an algorithm. When analyzing an algorithm, it is best to look at the worst-case running time. The best-case running time rarely occurs, and when you need a guaranteed performance time, only the worst-case running time can provide that. For an average-case running time, the same issue applies, along with the notion of what actually defines “average case”. A second possible definition of an efficient algorithm is an algorithm that achieves qualitatively better worst-case performance, at an analytical level, than a brute-force search. A brute-force search first obtains all possible solutions and then looks for a solution that satisfies the requirements. A more specific definition of efficiency further constrains the limitations by saying an algorithm is efficient if it has a polynomial run time. This means that it has a run time proportional to n^k, where k is a constant and n is the size of the input set. Defining such a specific definition of efficiency allows negatability, which means that it becomes possible to state that there is no efficient algorithm for a particular problem. To me, this means that there are simply some problems for which no efficient algorithm is achievable. Overall this section was generally understandable, a 7/10.
