1
00:00:00,000 --> 00:00:04,224
We had to learn a lot of details for each
algorithm we've covered in this course.
2
00:00:04,224 --> 00:00:08,067
Developers who need to implement their
own algorithms often need to choose
3
00:00:08,067 --> 00:00:11,122
an algorithm for each and
every problem they need to solve.
4
00:00:11,122 --> 00:00:14,826
And they often need to discuss their
decisions with other developers.
5
00:00:14,826 --> 00:00:19,494
Can you imagine needing to describe all
the algorithms in this same level of
6
00:00:19,494 --> 00:00:20,839
detail all the time?
7
00:00:20,839 --> 00:00:24,215
You'd spend all your time in
meetings rather than programming.
8
00:00:24,215 --> 00:00:28,700
That's why Big O Notation was created,
as a way of quickly describing how
9
00:00:28,700 --> 00:00:33,053
an algorithm performs as the data set
its working on increases in size.
10
00:00:33,053 --> 00:00:37,973
Big O Notation lets you quickly compare
several algorithms to choose the best one
11
00:00:37,973 --> 00:00:39,139
for your problem.
12
00:00:39,139 --> 00:00:42,461
The algorithms we've discussed in
this course are very well-known.
13
00:00:42,461 --> 00:00:46,430
Some job interviewers are going to
expect you to know their Big O runtimes.
14
00:00:46,430 --> 00:00:48,200
So let's look at them.
15
00:00:48,200 --> 00:00:52,499
Remember that the n in Big O Notation
refers to the number of elements you're
16
00:00:52,499 --> 00:00:53,381
operating on.
17
00:00:53,381 --> 00:00:57,322
With selection sort, you need to check
each item on the list to see if it's
18
00:00:57,322 --> 00:00:59,943
lowest so
you can move it over to the sorted list.
19
00:00:59,943 --> 00:01:02,571
So that's n operations.
20
00:01:02,571 --> 00:01:06,387
Suppose you're doing selection
sort on a list of 5 items, and
21
00:01:06,387 --> 00:01:08,048
in this case, would be 5.
22
00:01:08,048 --> 00:01:11,748
So that's 5 operations before you
can move an item to the sorted list.
23
00:01:11,748 --> 00:01:15,819
But with selection sort,
you have to loop over the entire list for
24
00:01:15,819 --> 00:01:17,531
each item you want to move.
25
00:01:17,531 --> 00:01:21,644
There are 5 items in the list, and you
have to do 5 comparisons to move each one.
26
00:01:21,644 --> 00:01:25,030
So it's more like 5 times 5 operations, or
27
00:01:25,030 --> 00:01:30,002
if we replace 5 with n,
it's n times n, or n squared.
28
00:01:30,002 --> 00:01:34,270
But wait, you might say, half of that
5 by 5 grid of operations is missing,
29
00:01:34,270 --> 00:01:38,140
because we're testing one few item
in the unsorted list with each pass.
30
00:01:38,140 --> 00:01:42,040
So isn't it more like,
1/2 times n times n?
31
00:01:42,040 --> 00:01:46,670
And this is true, we are not doing
a full n squared of operations.
32
00:01:46,670 --> 00:01:48,700
But remember, in Big O Notation,
33
00:01:48,700 --> 00:01:53,560
as the value of n gets really big,
constants like 1/2 become insignificant.
34
00:01:53,560 --> 00:01:55,620
And so we discard them.
35
00:01:55,620 --> 00:02:00,377
The Big O runtime of selection sort is
widely recognized as being O(n squared).
36
00:02:02,090 --> 00:02:06,453
Quicksort requires one operation for
each element of listed sorting.
37
00:02:06,453 --> 00:02:10,706
It needs to select a pivot first, and then
it needs to sort elements into lists that
38
00:02:10,706 --> 00:02:12,816
are less than or greater than the pivot.
39
00:02:12,816 --> 00:02:14,935
So that's n operations.
40
00:02:14,935 --> 00:02:18,607
To put that another way, if you have
a list of 8 items, then n is 8.
41
00:02:18,607 --> 00:02:22,770
So it will take 8 operations to
split the list around the pivot.
42
00:02:22,770 --> 00:02:26,810
But of course, the list isn't sorted after
splitting it around the pivot just once.
43
00:02:26,810 --> 00:02:29,920
You have to repeat those data
operations several times.
44
00:02:29,920 --> 00:02:33,130
In the best case you'll pick a pivot
that's right in the middle of the lists,
45
00:02:33,130 --> 00:02:36,180
so that you're dividing
list exactly in half.
46
00:02:36,180 --> 00:02:38,769
Then you keep dividing
the list in half until you
47
00:02:38,769 --> 00:02:40,526
have a list with a length of one.
48
00:02:40,526 --> 00:02:44,632
The number of times you need
to divide n in half until
49
00:02:44,632 --> 00:02:47,508
you reach one is expressed as log n.
50
00:02:47,508 --> 00:02:51,608
So you need to repeat n sorting
up rations log n times.
51
00:02:51,608 --> 00:02:57,493
That leaves us with the best case one
times for Quicksort of O (n log n).
52
00:02:57,493 --> 00:02:59,001
But that's the best case.
53
00:02:59,001 --> 00:03:00,596
What about the worst case?
54
00:03:00,596 --> 00:03:02,327
Well, if you pick the wrong pivot,
55
00:03:02,327 --> 00:03:04,712
you won't be dividing
the list exactly in half.
56
00:03:04,712 --> 00:03:06,480
If you pick a really bad pivot,
57
00:03:06,480 --> 00:03:10,837
the next recursive call to Quicksort
will only reduce the list length by 1.
58
00:03:10,837 --> 00:03:14,953
Since our Quicksort function simply
picks the first item to use as a pivot,
59
00:03:14,953 --> 00:03:18,088
we can make it pick the worst
possible pivot repeatedly,
60
00:03:18,088 --> 00:03:21,378
simply by giving it a list
that's sorted in reverse order.
61
00:03:21,378 --> 00:03:26,173
If we pick the worst possible pivot every
time, we'll have to split the list once
62
00:03:26,173 --> 00:03:30,487
for every item it contains, and
then, do n-sorting operations on it.
63
00:03:30,487 --> 00:03:35,008
You already know another sorting algorithm
that only manages to reduce the list by
64
00:03:35,008 --> 00:03:37,577
one element with each pass,
selection sort.
65
00:03:37,577 --> 00:03:40,692
Selection sort has
a runtime of O(n squared).
66
00:03:40,692 --> 00:03:44,450
And in the worst case,
that's the runtime for Quicksort as well.
67
00:03:44,450 --> 00:03:48,000
So which do we consider when trying
to decide whether to use Quicksort,
68
00:03:48,000 --> 00:03:50,280
the best case or the worst case?
69
00:03:50,280 --> 00:03:54,202
Well, as long as your implementation
doesn't just pick the first item as
70
00:03:54,202 --> 00:03:57,299
a pivot, which we did so
we could demonstrate this issue,
71
00:03:57,299 --> 00:04:01,960
it turns out that on average, Quicksort
performs closer to the best case.
72
00:04:01,960 --> 00:04:06,350
Many Quicksort implementations accomplish
this simply by picking a pivot at random
73
00:04:06,350 --> 00:04:08,420
on each recursive loop.
74
00:04:08,420 --> 00:04:12,420
Here we are sorting our reverse sorted
data again, but this time we picked pivots
75
00:04:12,420 --> 00:04:15,960
at random, which reduces the number
of recursive operations needed.
76
00:04:17,240 --> 00:04:19,720
Sure, random pivots sometimes
give you the best case and
77
00:04:19,720 --> 00:04:21,840
sometimes you'll randomly
get the worst case.
78
00:04:21,840 --> 00:04:26,282
But it all averages out over multiple
calls to the Quicksort function.
79
00:04:26,282 --> 00:04:28,800
Now, with Merge Sort,
there is no pivot to pick.
80
00:04:28,800 --> 00:04:33,373
Your list of n items always gets
divided in half log n times.
81
00:04:33,373 --> 00:04:38,638
That means, Merge Sort always has
a big O runtime of O(n log n).
82
00:04:38,638 --> 00:04:40,415
Contrast that with Quicksort,
83
00:04:40,415 --> 00:04:43,521
which only has a runtime of
O(n log n) in the best case.
84
00:04:43,521 --> 00:04:47,370
In the worst case,
Quicksort's runtime is O(n squared).
85
00:04:47,370 --> 00:04:51,750
And yet, out in the real world, Quicksort
is more commonly used than Merge Sort.
86
00:04:51,750 --> 00:04:55,460
Now, why is that if Quicksort's bigger
runtime can sometimes be worse than
87
00:04:55,460 --> 00:04:56,060
Merge Sort?
88
00:04:56,060 --> 00:05:00,480
This is one of those situations where
Big O Notation doesn't tell you
89
00:05:00,480 --> 00:05:01,730
the whole story.
90
00:05:01,730 --> 00:05:05,700
All Big O can tell you is the number
of times an operation is performed.
91
00:05:05,700 --> 00:05:08,930
It doesn't describe how
long that operation takes.
92
00:05:08,930 --> 00:05:11,490
And the operation merge of
performance repeatedly,
93
00:05:11,490 --> 00:05:15,662
takes longer than the operation
Quicksort performance repeatedly.
94
00:05:15,662 --> 00:05:18,780
Big O is a useful tool for
quickly describing how the runtime
95
00:05:18,780 --> 00:05:23,570
of an algorithm increases as the data set
it's operating on gets really, really big.
96
00:05:23,570 --> 00:05:27,395
But you can't always choose between two
algorithms based just on their Big O
97
00:05:27,395 --> 00:05:28,250
runtimes.
98
00:05:28,250 --> 00:05:31,760
Sometimes there is additional info
you need to know about an algorithm
99
00:05:31,760 --> 00:05:33,700
to make a good decision.
100
00:05:33,700 --> 00:05:35,530
Now that we can sort a list of items,
101
00:05:35,530 --> 00:05:39,090
we're well on our way to being able
to search a list efficiently as well.
102
00:05:39,090 --> 00:05:41,100
We'll look at how to do
that in the next stage.