This is an old revision of the document!
Table of Contents
Chapter 2
These two sections of chapter two deals with the efficiency of algorithms, as well as how an algorithm's running time changes as its input size changes. Both of these are important concepts, as algorithms must work quickly no matter what the scale of the problem.
Section 2.1(Computational Tractability)
This section is all about efficiency, even taking several attempts at defining it. The first attempt reads as follows:
“Proposed Definition of Efficiency (1): An algorithm is efficient if, when implemented, it runs quickly on in real input instances.“
This definition does not work because it has no concept of scale. An inefficient process could meet this standard if run on a very small data sample, since the computer could process things quickly. The next attempt reads as:
“Proposed Definition of Efficiency (2): An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search.“
This definition is simply too vague to work. It does not provide guidelines for that counts as “qualitatively better worst-case performance”, and is thus subjective. The final definition fixes this vagueness by providing a way of quantifying efficiency:
“Proposed Definition of Efficiency (3): An algorithm is efficient if it has a polynomial running time.“
This is the ideal definition for our purposes because of its specificity. It allows us to look at algorithms quantitatively so that we can determine whether a process is feasible. This definition also makes problems negatable. Thus, using this definition, we can decide when there is no efficient algorithm for a problem.
Section 2.2(Asymptotic Order of Growth)
This section looks at how an algorithm's worst-case running time grows as the input size grows. For our purposes as computer scientists, we do not need to stress out about finding the exact number of steps it takes to solve a problem. Instead, we make accurate generalizations in the form of O-notation so that algorithms' run times become easier to compare. This section begins by describing the specific process through which we can define an algorithm's upper and lower bounds, then describes how to find an algorithm's “tight bounds”. An algorithm has tight bounds if its upper-bound and lower-bound are the same function. This bound can sometimes also be found by calculating a limit as n goes to infinity.
The book then goes on to mention some of the properties of the asymptotic growth rates. It discusses transitivity, and sums of functions. 
