CS341 Lecture Notes - Intel 80386, Precautionary Statement, Quicksort
16 Oct 2011
School
Department
Course
Professor
Document Summary
Analysis of algorithms: we design algorithms to solve problems. What output should we get for each input: an algorithm is correct if for every input it finds (computes) the correct output. Running time: the running time of algorithm a on input x is the time that algorithm a requires to derive the correct output given x. We will denote this running time by ra(x). We use order notation to describe running time. Note: we did not mention running time of the program for a. Wall-clock time is not a good measure, as it is different from computer to computer, e. g. 80386 vs. pentium iii. Hence we remove details of the computer (exact speed of the processor, disk, memory, caching, etc. We count the number of elementary operations only. An elementary operation is an operation whose time can be bounded by a constant.
