Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Big O Runtime of Search Algorithms1:26 with Jay McGavren
Let's wrap up the course by looking at the Big O runtimes for Linear Search and Binary Search.
Quicksort Run Time (Worst Case)
Quicksort Run Time (Average Case)
O(n log n)
Merge Sort Run Time
O(n log n)
Linear Search Run Time
Binary Search Run Time
Let's wrap up the course by looking at the Big O run times for linear search and
These are going to be much simpler to calculate than the sorting
For linear search, you need to do one comparison to the target value for
each item in the list.
we could find the target value before searching the whole list.
But Big O notation is only concerned with the worst case,
where we have to search the entire list.
So for a list of eight items, that means eight operations.
The Big O run time for linear search is O(n),
where n is the number of items we're searching through.
This is also known as linear time.
Because when the number of items and
number of operations are compared on a graph, the result is a straight line.
Linear search looks pretty good, until you compare it to binary search.
For binary search, the number of items you have to search through, and therefore,
the number of operations, is cut in half with each comparison.
Remember, the number of times you can divide n by two until you reach one is
expressed as log n.
So the run time of binary search in Big O notation is O(log n).
Even for very large values event, that is very large lists you have to search
through, the number of operations needed to search is very small.
Binary search is a very fast, efficient algorithm.
That's our tour of sorting and searching algorithms.
Be sure to check the teacher's notes for opportunities to learn more.
Thanks for watching.
You need to sign up for Treehouse in order to download course files.Sign up