This is an old revision of the document!
Chapter 2
2.1: Computational Tractability The goal o this course is to write correct and efficient algorithms and this sections goes through how we define efficiency.
Intial attempt at defining efficiancy: “An algorithm is efficient if when, when implemented, it runs quickly on real input instances” What works:
- Good initial intro to what we want. Need to get things done quickly!
What doesn't work:
- Too vague: need where and how well
- Will it be fast on more than just small cases?
- What are real input instances?
Worst-Case Running Times and Brute-Force Search: “An algorith is efficient if it achieves qualitatviely better worst-case performance, at an analytical level, than brute-force search” Why it works:
- brute-force search is just going through each option so imporving is needed.
- shows intrinsic structure and computational tractability about the problem
Why it doesn't works:
- qualitatively better performance is too vague
Polynomial Time as a Definition of Efficiency “An algorithm is efficient if it has a polynomial running time.” Why it works:
- very specific
- makes it easier to prove there is no efficient algorithm
Why it doesn't work
- Too specific
2.2 Asymptotic Order of Growth
