01:198:107 Lecture Notes - Lecture 14: Selection Sort, Artery Recordings, Insertion Sort
5 Mar 2018
School
Department
Course
Professor
Document Summary
We would like to make general statements about one algorithm being faster than another. There are too many variables to use actual time to compare algorithms. Count should model work done by algorithm. Problem: number of operations depends on size of input. Just because inputs the same size doesn"t mean the input is the same. A list sorted backwards of length n. Worst case: o(x) (what is the absolute worst) Function f(n) grows asymptotically faster than g(n) if at some point, and forever after that point, f>g. Focus on what happens as n grows large. There are many ways to sort data. More than one way to do something. Fast to write vs fast to run. One by one add numbers to the sorted vector. Moving numbers already there to make room. We don"t really need two vectors, unsorted and sorted-we can keep all the data in one vector. Common technique: use separate regions of a vector for different things.
