This is an old revision of the document!


Chapter 2 - Basics of Algorithm Analysis

We have to think about how much time and how much space an algorithm will use as the size of its input(s) increases.

2.1 - Computational Tractability

Many problems involve searching through a large number of possibilities, and the algorithm is supposed to find a solution more quickly than just searching through all theoretical possibilities. A basic definition of efficiency is as follows: “An algorithm is efficient if, when implemented, it runs quickly on real input instances.” This obviously leads to questions like how fast is “quickly” and how do we define “real input instances”, especially if the data set could be scaled up significantly.

courses/cs211/winter2011/journals/david/chapter2.1295401214.txt.gz · Last modified: by margoliesd
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0