1
00:00:05,200 --> 00:00:09,565
Ok, what do we mean by best case, 
worst case and average case? 

2
00:00:09,840 --> 00:00:15,150
We saw that our Bubble sort code only performed 
11 comparisons, when the data was nearly sorted. 

3
00:00:15,360 --> 00:00:21,365
I'll run bubble_sort.py again, because we haven't 
tested the changes that we made in the last video. 

4
00:00:23,840 --> 00:00:29,640
The comparison count is 11, which is much lower 
than the 21 that we were getting, with the other 2 lists — 

5
00:00:29,640 --> 00:00:35,360
that's the ones on lines 23 and 24.
When we refer to best case, or worst case, 

6
00:00:35,360 --> 00:00:39,643
we're generally talking about the nature of 
the data that our algorithms are processing. 

7
00:00:39,680 --> 00:00:43,840
Let's see how Bubble sort performs, 
when the data is already sorted. 

8
00:00:59,840 --> 00:01:05,247
When we run that,
the number of comparisons drops to 6. 

9
00:01:05,600 --> 00:01:11,140
Our optimised Bubble sort makes n - 1 comparisons, 
when working with data that's already sorted. 

10
00:01:11,360 --> 00:01:14,936
That's the best case, for 
Bubble sort, and is O(n). 

11
00:01:15,200 --> 00:01:17,843
What's the worst case, for Bubble sort? 

12
00:01:18,194 --> 00:01:23,280
We've already seen that, in fact. It's 
when the data is sorted in reverse order. 

13
00:01:23,280 --> 00:01:29,225
I'll uncomment line 24, and comment out 
line 26, so we're using the reversed data: 

14
00:01:32,240 --> 00:01:33,707
Run the program, 

15
00:01:35,520 --> 00:01:41,207
and it gives a comparison count of 21.
So for Bubble sort, the worst case is n squared. 

16
00:01:41,813 --> 00:01:44,880
We get the worst case 
when the data is in reverse order. 

17
00:01:44,880 --> 00:01:48,960
Be aware that the same data doesn't 
necessarily relate to the best or worst case, 

18
00:01:48,960 --> 00:01:50,808
for different algorithms. 

19
00:01:50,880 --> 00:01:55,325
For example, the best case for Bubble 
sort is when the data is already sorted. 

20
00:01:55,440 --> 00:02:00,294
But a commonly used algorithm, Quicksort, 
performs worst with sorted data. 

21
00:02:00,480 --> 00:02:04,978
Merge sort and Heap sort also perform 
badly, when the data is nearly sorted. 

22
00:02:05,040 --> 00:02:08,726
With those three algorithms, 
sorted data is their worst case. 

23
00:02:08,960 --> 00:02:12,000
There's an interesting set of 
animations, on the internet, 

24
00:02:12,000 --> 00:02:16,446
that show how much work each sorting 
algorithm has to do, with nearly sorted data. 

25
00:02:16,640 --> 00:02:21,380
I'll visit that page in my browser, 
and put the link in the resources. 

26
00:02:22,284 --> 00:02:26,160
I won't do it on video, but it's 
interesting to click the various images, 

27
00:02:26,160 --> 00:02:30,560
and play them, to see the differences.
I'll click the large Play button, 

28
00:02:30,560 --> 00:02:35,840
which plays them all at the same time, 
and you can see which ones finish first. 

29
00:02:36,560 --> 00:02:42,240
This emphasises the point I made earlier. Data 
that provides the best case, for one algorithm, 

30
00:02:42,240 --> 00:02:47,040
might be the worst case for a different algorithm.
I said that Bubble sort was a bit rubbish, 

31
00:02:47,040 --> 00:02:53,920
and it's rarely used these days. But it does 
perform well with sorted, or nearly sorted, data. 

32
00:02:53,920 --> 00:02:57,280
Ok, that's the end of our 
discussion of Big O notation. 

33
00:02:57,360 --> 00:03:00,720
I'll finish the section with 
a summary, in the next video.