**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

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 up