[MUSIC]
So now we're ready to put together everything we've been talking
about with performance analysis.
And in particular think about the asymptotic balance,
the big-O classes of searching algorithms.
So at this point we've got two searching algorithms that we've talked about, so
by the end of this video you'll be able to both state and
justify the big-O runtime for both of these search algorithms.
And both in the best case and in the worst case.
So what we're going to be doing is filling in this little table, and
so let's start with a linear search.
So our linear search basic algorithm is that when we're searching
through a list of data, we start at the beginning and we go to the end, and
we look for our desired piece of data.
So, in the best case, let's think back to
the example in your search that we've done, that was that hasLetter method,
in the best case we find the piece of data right away.
And so, our best case performance is a constant time big O(1).
Now in the worst case, we talked about this also with the hasLetter method.
What happens if we're unlucky is that we go through the entire string or
entire list of data and we don't find what we're looking for, or
we only find it at the very end.
But in either one of those situations in this very unlucky situation, we have to go
through all data and so our performance is growing just like the input is.
So, it's big O(n).
And so if the worst case linear search performs like big O(n).
Okay, so we've got linear search and now let's move on to binary search.
We haven't talked about binary search in this course so far, but
if you think back to the first course in the specialization we did do several
examples with this algorithm.
And so you can go back there to refresh your memory.
The binary search algorithm is similarly as before looking for
data in a list of data, but something that we have
to assume in order to use binary search is that this data is already sorted.
It's organized from smallest to biggest in some measure of order.
Okay, so if we make that assumption that we have sorted data,
what's the best case situation?
What's the worst case situation?
Well, we have to go back to what the algorithm is in the first place before we
can analyze it.
So the nuts and bolts of the binary search algorithm is that we take our data and
we start by looking in the very middle.
And maybe we're lucky and we found it.
Sweet.
If not, if we didn't find the item that we're looking for
in the very middle then what we have to do is either look at the first half
of the list or the second half of the list.
And we choose which half to look at based on comparing the value that we're looking
for with the value in the middle and seeing, should I be before it or
should I be after it?
And so what we're doing in binary search is over and
over cutting the amount of information that we need to look at in half again and
again and again until we focus in onto where our element
ought to be in the list and then checking if it really is there.
Okay so that's big picture what we're doing, now how does it perform?
And we ask ourselves, best case, worst case?
And best case is super lucky, we zoom into the middle of the list and
we've found our element that we're looking for.
And we're done and we can return, and that took lots of time.
So the best case is really a similar situation to linear search,
where we're really lucky and we find our item at the first chance we could.
So the very first thing that we test is actually
the element that we're looking for.
Okay, so that's the best case, constant time, okay.
But what about the worst case?
And let's think through what happens in this worst case and
what it would mean to have a really unlucky search.
And just like before, what it would mean to have a really unlucky search is if we
don't find the element at all.
If we keep looking, keep looking, keep looking, and
we can't find this element in the list.
So if the element is missing from the list, and
let's think about what this algorithm would do in that that case.
So we looked in the middle, and we didn't find our element.
And now, we go and look at just half the list, and
then we basically repeat the algorithm.
And so what we do is we look in the middle of that half and look for our algorithm,
and we're not gonna find it there.
And so we look at half of the remaining and look in the middle of that.
We're not gonna find it there.
Okay, so we only need to consider half of the remaining.
Look in the middle of that, keep on going, keep on going, and
the question is when do we get to stop?
So, every time we repeat this process, every time we
have a new high element and a low element, and we compute a new midpoint,
what we're doing is we're decreasing the list in consideration by half.
And so we get to stop when the number of elements that we need to consider,
well, is just one.
And so we need to ask ourselves, how many times does it take for
this process to reduce the list that we need to consider to just one element?
Or another way of saying that is,
how many times can we divide the size of the element by 2 and get to 1?
So, we're repeatedly dividing by 2, dividing by 2, dividing by 2,
and we want to get to 1.
But the number of times we can do that is
exactly the logarithm base 2 of the size of our list.
And there's a support video to go through that calculation a little bit
more in detail if you're interested.
So, for binary search we filled in that last cell in the table, and
in the worst case this search runs in big O of logarithmic time.
So, we've got this table, it's great.
But, we've got that little asterisk that says, all of these calculations for
binary search are assuming that our data is sorted.
Our algorithm for binary search requires the data to be sorted.
And so it's not really fair to have this table and
compare linear search head to head with binary search because linear search
doesn't make any assumptions on the organization of the data.
And so if we really wanted to compare them head to head,
these two algorithms, what we would need to do is say, well, how long would it take
to take an unorganized list and sort it and then run binary search on it?
So in the next video we'll be summarizing some approaches for sorting and
doing their performance analysis as well.
Christine AlvaradoAssociate Teaching Professor
Mia MinnesAssistant Teaching Professor
Leo PorterAssistant Teaching Professor
