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

The algorithms we've discussed in this stage are very well-known, and some job interviewers are going to expect you to know their Big O runtimes. So let's look at them!

#### Quicksort Run Time (Worst Case)

O(n²)

#### Quicksort Run Time (Average Case)

O(n log n)

#### Merge Sort Run Time

O(n log n)

We had to learn a lot of details for each
algorithm we've covered in this course.
0:00

Developers who need to implement their
own algorithms often need to choose
0:04

an algorithm for each and
every problem they need to solve.
0:08

And they often need to discuss their
decisions with other developers.
0:11

Can you imagine needing to describe all
the algorithms in this same level of
0:14

detail all the time?
0:19

You'd spend all your time in
meetings rather than programming.
0:20

That's why Big O Notation was created,
as a way of quickly describing how
0:24

an algorithm performs as the data set
its working on increases in size.
0:28

Big O Notation lets you quickly compare
several algorithms to choose the best one
0:33

for your problem.
0:37

The algorithms we've discussed in
this course are very well-known.
0:39

Some job interviewers are going to
expect you to know their Big O runtimes.
0:42

So let's look at them.
0:46

Remember that the n in Big O Notation
refers to the number of elements you're
0:48

operating on.
0:52

With selection sort, you need to check
each item on the list to see if it's
0:53

lowest so
you can move it over to the sorted list.
0:57

So that's n operations.
0:59

Suppose you're doing selection
sort on a list of 5 items, and
1:02

in this case, would be 5.
1:06

So that's 5 operations before you
can move an item to the sorted list.
1:08

But with selection sort,
you have to loop over the entire list for
1:11

each item you want to move.
1:15

There are 5 items in the list, and you
have to do 5 comparisons to move each one.
1:17

So it's more like 5 times 5 operations, or
1:21

if we replace 5 with n,
it's n times n, or n squared.
1:25

But wait, you might say, half of that
5 by 5 grid of operations is missing,
1:30

because we're testing one few item
in the unsorted list with each pass.
1:34

So isn't it more like,
1/2 times n times n?
1:38

And this is true, we are not doing
a full n squared of operations.
1:42

But remember, in Big O Notation,
1:46

as the value of n gets really big,
constants like 1/2 become insignificant.
1:48

And so we discard them.
1:53

The Big O runtime of selection sort is
widely recognized as being O(n squared).
1:55

Quicksort requires one operation for
each element of listed sorting.
2:02

It needs to select a pivot first, and then
it needs to sort elements into lists that
2:06

are less than or greater than the pivot.
2:10

So that's n operations.
2:12

To put that another way, if you have
a list of 8 items, then n is 8.
2:14

So it will take 8 operations to
split the list around the pivot.
2:18

But of course, the list isn't sorted after
splitting it around the pivot just once.
2:22

You have to repeat those data
operations several times.
2:26

In the best case you'll pick a pivot
that's right in the middle of the lists,
2:29

so that you're dividing
list exactly in half.
2:33

Then you keep dividing
the list in half until you
2:36

have a list with a length of one.
2:38

The number of times you need
to divide n in half until
2:40

you reach one is expressed as log n.
2:44

So you need to repeat n sorting
up rations log n times.
2:47

That leaves us with the best case one
times for Quicksort of O (n log n).
2:51

But that's the best case.
2:57

What about the worst case?
2:59

Well, if you pick the wrong pivot,
3:00

you won't be dividing
the list exactly in half.
3:02

If you pick a really bad pivot,
3:04

the next recursive call to Quicksort
will only reduce the list length by 1.
3:06

Since our Quicksort function simply
picks the first item to use as a pivot,
3:10

we can make it pick the worst
possible pivot repeatedly,
3:14

simply by giving it a list
that's sorted in reverse order.
3:18

If we pick the worst possible pivot every
time, we'll have to split the list once
3:21

for every item it contains, and
then, do n-sorting operations on it.
3:26

You already know another sorting algorithm
that only manages to reduce the list by
3:30

one element with each pass,
selection sort.
3:35

Selection sort has
a runtime of O(n squared).
3:37

And in the worst case,
that's the runtime for Quicksort as well.
3:40

So which do we consider when trying
to decide whether to use Quicksort,
3:44

the best case or the worst case?
3:48

Well, as long as your implementation
doesn't just pick the first item as
3:50

a pivot, which we did so
we could demonstrate this issue,
3:54

it turns out that on average, Quicksort
performs closer to the best case.
3:57

Many Quicksort implementations accomplish
this simply by picking a pivot at random
4:01

on each recursive loop.
4:06

Here we are sorting our reverse sorted
data again, but this time we picked pivots
4:08

at random, which reduces the number
of recursive operations needed.
4:12

Sure, random pivots sometimes
give you the best case and
4:17

sometimes you'll randomly
get the worst case.
4:19

But it all averages out over multiple
calls to the Quicksort function.
4:21

Now, with Merge Sort,
there is no pivot to pick.
4:26

Your list of n items always gets
divided in half log n times.
4:28

That means, Merge Sort always has
a big O runtime of O(n log n).
4:33

Contrast that with Quicksort,
4:38

which only has a runtime of
O(n log n) in the best case.
4:40

In the worst case,
Quicksort's runtime is O(n squared).
4:43

And yet, out in the real world, Quicksort
is more commonly used than Merge Sort.
4:47

Now, why is that if Quicksort's bigger
runtime can sometimes be worse than
4:51

Merge Sort?
4:55

This is one of those situations where
Big O Notation doesn't tell you
4:56

the whole story.
5:00

All Big O can tell you is the number
of times an operation is performed.
5:01

It doesn't describe how
long that operation takes.
5:05

And the operation merge of
performance repeatedly,
5:08

takes longer than the operation
Quicksort performance repeatedly.
5:11

Big O is a useful tool for
quickly describing how the runtime
5:15

of an algorithm increases as the data set
it's operating on gets really, really big.
5:18

But you can't always choose between two
algorithms based just on their Big O
5:23

runtimes.
5:27

Sometimes there is additional info
you need to know about an algorithm
5:28

to make a good decision.
5:31

Now that we can sort a list of items,
5:33

we're well on our way to being able
to search a list efficiently as well.
5:35

We'll look at how to do
that in the next stage.
5:39

You need to sign up for Treehouse in order to download course files.

Sign up