1 00:00:00,380 --> 00:00:04,290 Let's wrap up the course by looking at the Big O run times for linear search and 2 00:00:04,290 --> 00:00:05,480 binary search. 3 00:00:05,480 --> 00:00:08,740 These are going to be much simpler to calculate than the sorting 4 00:00:08,740 --> 00:00:10,010 algorithms were. 5 00:00:10,010 --> 00:00:13,870 For linear search, you need to do one comparison to the target value for 6 00:00:13,870 --> 00:00:15,360 each item in the list. 7 00:00:15,360 --> 00:00:16,550 Again, theoretically, 8 00:00:16,550 --> 00:00:19,450 we could find the target value before searching the whole list. 9 00:00:19,450 --> 00:00:22,639 But Big O notation is only concerned with the worst case, 10 00:00:22,639 --> 00:00:24,907 where we have to search the entire list. 11 00:00:24,907 --> 00:00:29,240 So for a list of eight items, that means eight operations. 12 00:00:29,240 --> 00:00:32,012 The Big O run time for linear search is O(n), 13 00:00:32,012 --> 00:00:35,433 where n is the number of items we're searching through. 14 00:00:35,433 --> 00:00:37,471 This is also known as linear time. 15 00:00:37,471 --> 00:00:39,464 Because when the number of items and 16 00:00:39,464 --> 00:00:43,792 number of operations are compared on a graph, the result is a straight line. 17 00:00:43,792 --> 00:00:47,864 Linear search looks pretty good, until you compare it to binary search. 18 00:00:47,864 --> 00:00:52,227 For binary search, the number of items you have to search through, and therefore, 19 00:00:52,227 --> 00:00:55,555 the number of operations, is cut in half with each comparison. 20 00:00:55,555 --> 00:01:00,064 Remember, the number of times you can divide n by two until you reach one is 21 00:01:00,064 --> 00:01:01,321 expressed as log n. 22 00:01:01,321 --> 00:01:06,710 So the run time of binary search in Big O notation is O(log n). 23 00:01:06,710 --> 00:01:10,720 Even for very large values event, that is very large lists you have to search 24 00:01:10,720 --> 00:01:14,510 through, the number of operations needed to search is very small. 25 00:01:14,510 --> 00:01:18,550 Binary search is a very fast, efficient algorithm. 26 00:01:18,550 --> 00:01:21,400 That's our tour of sorting and searching algorithms. 27 00:01:21,400 --> 00:01:25,090 Be sure to check the teacher's notes for opportunities to learn more. 28 00:01:25,090 --> 00:01:26,000 Thanks for watching.