01:198:111 Lecture Notes - Lecture 25: Binary Search Algorithm, Linear Search, Lyft
28 Nov 2018
School
Department
Course
Professor
01:198:111 verified notes
25/28View all
Document Summary
Think about how much we search each day. When searching when we want to determine how efficient the searching program is. N is the number of items, which affect how long it takes for the program to run. Linear searching efficiency in terms of n. Note: there are two worst cases, either the element is at the end or not there, but the answer is stil. Practically average case is better than worst case, but from a theoretical standpoint they are the same, given any input. Binary searching efficiency in terms of n, and if array is sorted. All the same, however while best case is not as good as a linear search, overall the binary search is more efficient. For an input of one million or 2^20 n terms, the linear search at the worst will take a million operations to run. Binary search will only take 20 and thus much more efficient for larger data sets.
