Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic 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

0:00
Let's wrap up the course by looking at the Big O run times for linear search and

0:04
binary search.

0:05
These are going to be much simpler to calculate than the sorting

0:08
algorithms were.

0:10
For linear search, you need to do one comparison to the target value for

0:13
each item in the list.

0:15
Again, theoretically,

0:16
we could find the target value before searching the whole list.

0:19
But Big O notation is only concerned with the worst case,

0:22
where we have to search the entire list.

0:24
So for a list of eight items, that means eight operations.

0:29
The Big O run time for linear search is O(n),

0:32
where n is the number of items we're searching through.

0:35
This is also known as linear time.

0:37
Because when the number of items and

0:39
number of operations are compared on a graph, the result is a straight line.

0:43
Linear search looks pretty good, until you compare it to binary search.

0:47
For binary search, the number of items you have to search through, and therefore,

0:52
the number of operations, is cut in half with each comparison.

0:55
Remember, the number of times you can divide n by two until you reach one is

1:00
expressed as log n.

1:01
So the run time of binary search in Big O notation is O(log n).

1:06
Even for very large values event, that is very large lists you have to search

1:10
through, the number of operations needed to search is very small.

1:14
Binary search is a very fast, efficient algorithm.

1:18
That's our tour of sorting and searching algorithms.

1:21
Be sure to check the teacher's notes for opportunities to learn more.

1:25
Thanks for watching.
You need to sign up for Treehouse in order to download course files.
Sign up