This is an old revision of the document!
Table of Contents
Chapter 2
2.1 Computational Tractability
Summary
The author talks about why worst-case approach the complexity is used rather than its seemingly attractive alternative—average performance. It is hard to define what random input should we generate to evaluate the complexity.
two important definitions:
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. =⇒ quantify “qualitatively better” =⇒ polytime
Proposed Definition of Efficiency (3)“ An algorithm is efficient if it has a polynomial running time.
The author concludes that there is a final, fundamental benefit to making our definition of efficiency so specific: it becomes negatable. It becomes possible to express the notion that there is no efficient algorithm for a particular problem.
Readable: 7/Interesting: 5
2.2 Asymptotic Order of Growth
Summary the way we quantitatively measure the complexity is intrinsically based on the worst case analysis. We provide a upper bound where the runtime is bounded by some other c*F(n) and also a lower bound where the runtime function is lower bounded by some Omega(n). The author then talks about some asymtotic bounds for common functions such as poynomials, exponentials, and logarithms. And showed their asymtotic bounds.
Readable: 7/Interesting: 2
2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays
SUMMARY This section covers the discussion as to the underlying data structure to implement the stable matching algorithm. The discussion is essentially about the tradeoffs of using a list versus an array. Comparison:
Array: fast, constant time to access an element given an index. List: more flexible, but slower to access each element. O(N).
Array Add element O(1) Delete element O(N) Find element O(N) List Add element O(1) Delete element O(1) Find element O(N)
