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.