CMPT 225 Lecture Notes - Lecture 4: Sorting Algorithm, Insertion Sort, Binary Search Algorithm
4 Sep 2013
School
Department
Course
Professor
Document Summary
How performance varies for different input of same size based on organization of the data. May be asked what an array should look like to be best/avg/worst case for an algorithm. Although useful, can be difficult to determine exact num of operations by an algorithm. Is instruction executed most times in an algorithm. Number of times this is executed is usually proportional to the running time of the algorithm. If array isn"t sorted, use linear search (it"s the only way to do it) - start with first item, compare each item to target, if find, return true, else never find, return false. Linear search barometer instruction: equality checking (comparisons) arr[i] == x. Best case: 1, item looking for is first item in array make comparison arr[i] == x once. Worst case: length of the array, or not in the array. Both cases: have to go through entire thing.
