Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Start a free Courses trial
to watch this video
Let's wrap up the course by looking at the Big O runtimes for Linear Search and Binary Search.
Quicksort Run Time (Worst Case)
O(nĀ²)
Quicksort Run Time (Average Case)
O(n log n)
Merge Sort Run Time
O(n log n)
Linear Search Run Time
O(n)
Binary Search Run Time
O(log n)
Learning More
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
Let's wrap up the course by looking at
the Big O run times for linear search and
0:00
binary search.
0:04
These are going to be much simpler
to calculate than the sorting
0:05
algorithms were.
0:08
For linear search, you need to do one
comparison to the target value for
0:10
each item in the list.
0:13
Again, theoretically,
0:15
we could find the target value
before searching the whole list.
0:16
But Big O notation is only
concerned with the worst case,
0:19
where we have to search the entire list.
0:22
So for a list of eight items,
that means eight operations.
0:24
The Big O run time for
linear search is O(n),
0:29
where n is the number of items
we're searching through.
0:32
This is also known as linear time.
0:35
Because when the number of items and
0:37
number of operations are compared on
a graph, the result is a straight line.
0:39
Linear search looks pretty good,
until you compare it to binary search.
0:43
For binary search, the number of items you
have to search through, and therefore,
0:47
the number of operations,
is cut in half with each comparison.
0:52
Remember, the number of times you can
divide n by two until you reach one is
0:55
expressed as log n.
1:00
So the run time of binary search
in Big O notation is O(log n).
1:01
Even for very large values event, that
is very large lists you have to search
1:06
through, the number of operations
needed to search is very small.
1:10
Binary search is a very fast,
efficient algorithm.
1:14
That's our tour of sorting and
searching algorithms.
1:18
Be sure to check the teacher's notes for
opportunities to learn more.
1:21
Thanks for watching.
1:25
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up