1
00:00:05,024 --> 00:00:09,904
Big O is used to describe the complexity 
of an algorithm, as its input increases. 

2
00:00:10,080 --> 00:00:14,467
Complexity can refer to execution time, 
or space requirements. 

3
00:00:14,467 --> 00:00:21,050
For example, Merge sort has a worst case time complexity 
of O(n log n) and a space complexity of O(n). 

4
00:00:21,120 --> 00:00:24,835
If memory is an issue, then 
you may prefer Heap sort. 

5
00:00:26,880 --> 00:00:30,080
Heap sort has a worst case 
time complexity of O(n log n), 

6
00:00:30,080 --> 00:00:34,467
the same as Merge sort. But 
its space complexity is O(1). 

7
00:00:34,560 --> 00:00:38,160
What that tells us, is that Merge 
sort will use more and more memory, 

8
00:00:38,160 --> 00:00:42,704
as the size of the data increases.
Heap sort doesn't need more memory. 

9
00:00:43,040 --> 00:00:48,000
O(1) is constant, and doesn't change, 
when you have more data to process. 

10
00:00:50,480 --> 00:00:53,534
Big O doesn't describe how long 
an algorithm will take to run. 

11
00:00:53,760 --> 00:00:59,650
It describes how the time will increase, as the 
number of inputs (the size of the data) increases. 

12
00:00:59,920 --> 00:01:03,517
Similarly, it doesn't describe 
how much memory will be used. 

13
00:01:03,760 --> 00:01:08,034
It describes how the memory requirement 
will increase, as n gets larger. 

14
00:01:10,560 --> 00:01:15,484
In this section, you've seen how various Big O 
notations describe the complexity of an algorithm. 

15
00:01:15,680 --> 00:01:19,760
You've also seen how to implement a 
simple sorting algorithm — Bubble sort. 

16
00:01:19,840 --> 00:01:22,480
You probably wouldn't use 
bubble sort in a real program, 

17
00:01:22,480 --> 00:01:25,840
but it does give a good idea of 
what a sorting algorithm does. 

18
00:01:25,840 --> 00:01:29,764
You also saw the steps that you can 
take, when optimising your code. 

19
00:01:32,240 --> 00:01:35,501
There are no hard and fast rules 
for how to optimise your code. 

20
00:01:35,760 --> 00:01:39,620
There are a lot of techniques available 
— in the Dictionaries and sets section, 

21
00:01:39,620 --> 00:01:42,701
you saw that using a set can 
give a huge performance increase, 

22
00:01:42,701 --> 00:01:46,133
rather than using a list.
The two optimisations, 

23
00:01:46,133 --> 00:01:50,350
that we made to the bubble sort code, 
demonstrated the steps that you can follow. 

24
00:01:50,560 --> 00:01:54,223
We started out by understanding 
exactly what the code was doing. 

25
00:01:56,320 --> 00:01:59,779
Once you understand that, you can 
look for patterns and short-cuts. 

26
00:02:00,080 --> 00:02:03,203
Reducing the number of 
iterations, of our inner loop, 

27
00:02:03,203 --> 00:02:07,920
had a significant impact on the performance.
We also stored the length of the list, 

28
00:02:07,920 --> 00:02:11,733
in a variable, to save calling 
the len function repeatedly. 

29
00:02:14,320 --> 00:02:18,925
Writing efficient code comes with experience.
When you're starting to learn programming, 

30
00:02:18,925 --> 00:02:25,040
you'll be pleased just to produce code that works.
Be pleased — and proud. Your early code won't be 

31
00:02:25,040 --> 00:02:28,800
perfect, and it doesn't have to be.
The more code you write, 

32
00:02:28,800 --> 00:02:33,680
the better your code will become.
Practise, write lots of code, and you'll find that 

33
00:02:33,680 --> 00:02:42,640
each program will be better than the previous one.
I'll see you in the next section.