1
00:00:05,200 --> 00:00:08,800
Before we look at some graphs, to 
see how the complexities increase, 

2
00:00:08,800 --> 00:00:12,960
there are a few points to be aware of.
Big O measures the complexity of an algorithm 

3
00:00:12,960 --> 00:00:18,160
as its input grows. It doesn't tell you how long 
the algorithm will take to complete, it indicates 

4
00:00:18,160 --> 00:00:23,200
how its time increases with larger inputs.
If two functions are both O(n), that doesn't 

5
00:00:23,200 --> 00:00:28,320
mean they take the same time to execute. 
It means that, however long each one takes, 

6
00:00:28,320 --> 00:00:33,860
it will take about ten times as long to 
process 1,000 items as it does to process 100. 

7
00:00:36,080 --> 00:00:40,509
Some calculations really are very 
complex. If something is O n squared, 

8
00:00:40,509 --> 00:00:44,560
then it will take a long time with large n.
Unless you can come up with a more efficient 

9
00:00:44,560 --> 00:00:48,560
algorithm that does the same job, you're 
stuck with that. But understanding the 

10
00:00:48,560 --> 00:00:53,280
complexity allows you to make decisions, 
such as doing the processing over night. 

11
00:00:53,280 --> 00:00:57,840
Executing code that runs in factorial time, 
while a customer's waiting on the telephone, 

12
00:00:57,840 --> 00:01:01,120
is something you might want to reconsider.
Don't worry if you don't know what 

13
00:01:01,120 --> 00:01:06,677
logarithms are. All you really need to 
understand, is how quickly things grow. 

14
00:01:08,720 --> 00:01:13,886
On this graph, we can see how each of the 
big O types increase, as n gets larger. 

15
00:01:14,320 --> 00:01:19,880
The constant time line, O(1), is the blue, 
horizontal line along the bottom of the chart. 

16
00:01:20,000 --> 00:01:24,397
The time remains constant, no 
matter how many items we process. 

17
00:01:25,520 --> 00:01:29,836
The red line represents O(log n).
That increases quite slowly. 

18
00:01:29,836 --> 00:01:36,830
We've seen that log to base 2 of 1000 is about 10.
Using logs to base 10, log(1000) is 3. 

19
00:01:37,280 --> 00:01:40,883
The big O notation doesn't use 
any particular base for log n. 

20
00:01:40,960 --> 00:01:45,120
As programmers, we tend to think 
of base 2 (binary), but O(log n) 

21
00:01:45,120 --> 00:01:51,840
increases slowly whichever base is used.
O(n) is represented by the yellow line. 

22
00:01:51,840 --> 00:01:54,880
That's growing a lot faster than the first 2 lines. 

23
00:01:54,880 --> 00:01:58,992
The scale of the graph doesn't really 
represent how much quicker O(n) is increasing. 

24
00:01:59,360 --> 00:02:03,360
If we extended the graph right, 
to show the values for 125, 

25
00:02:03,360 --> 00:02:08,072
O(n) would be at the top right of the chart.
O log 10 n would be about 2. 

26
00:02:09,360 --> 00:02:13,840
O(n log n) is represented by the green line.
Even with this limited range for n, 

27
00:02:13,840 --> 00:02:18,517
from 1 to 10, you can see that it 
increases faster than the first 3 lines. 

28
00:02:18,517 --> 00:02:24,117
Many sorting functions run in n log n 
time. Sorting is quite a slow operation. 

29
00:02:25,280 --> 00:02:30,065
Now we get to algorithms that are really costly. 
They'll take a long time to complete, 

30
00:02:30,065 --> 00:02:35,172
as the amount of data they're working with increases.
O n squared is increasing quickly. 

31
00:02:35,172 --> 00:02:39,709
With 1000 items to process,
n squared will be 1 million. 

32
00:02:40,640 --> 00:02:44,400
If you create an algorithm that runs 
in O(n!) time, then you're trying to 

33
00:02:44,400 --> 00:02:49,680
calculate something that's very complex.
As you can see, O(n!) grows so quickly that 

34
00:02:49,680 --> 00:02:57,000
we can only fit the first 5 values on the chart.
6 factorial is 720, which is way off the top. 

35
00:02:58,960 --> 00:03:01,520
You might have found some of that a bit scary! 

36
00:03:01,520 --> 00:03:05,360
Don't worry if you don't understand it 
all. The main thing you're interested in, 

37
00:03:05,360 --> 00:03:10,560
is how the complexity affects the performance 
(or space requirements) of your code. 

38
00:03:10,560 --> 00:03:16,400
For example, an O(n) algorithm will slow down 
more than an O(log n) algorithm, as n gets larger. 

39
00:03:16,400 --> 00:03:21,920
As you process more and more data, in other words.
Just in case the charts were confusing, 

40
00:03:21,920 --> 00:03:26,227
on the next slide we can see values 
for each of the orders we discussed. 

41
00:03:28,160 --> 00:03:34,280
The table shows how the various orders increase, 
as we process 10 times as much data, on each row. 

42
00:03:34,400 --> 00:03:38,320
If you come across an order that we haven't 
discussed, use your spreadsheet to calculate 

43
00:03:38,320 --> 00:03:43,040
the values of the expression.
For example, I mentioned that 

44
00:03:43,040 --> 00:03:48,480
there was an optimisation that reduces the travelling
salesman problem to n squared 2 * 2 to the power n.

45
00:03:48,480 --> 00:03:55,147
In the last column, I've calculated the values of
n squared * 2 to the power n, for each value of n. 

46
00:03:56,160 --> 00:04:01,096
As you can see, it grows a lot slower 
than a factorial time (n!) algorithm. 

47
00:04:01,096 --> 00:04:11,374
When n is 100, n! is 9 followed by 157 zeros. 
That's what 9E+157 means — and it's a huge number. 

48
00:04:12,160 --> 00:04:19,360
n squared * 2 to the power n is 1E+34, which is a
1 followed by 34 zeros. That's still huge, 

49
00:04:19,360 --> 00:04:24,320
but a lot smaller than n!
The blank cells, by the way, are because my 

50
00:04:24,320 --> 00:04:30,320
spreadsheet couldn't handle numbers that large.
It should be obvious that Big O doesn't tell 

51
00:04:30,320 --> 00:04:35,520
you exactly how long an algorithm will take to 
execute, nor how many operations it will perform. 

52
00:04:35,520 --> 00:04:39,520
log 1 is zero, and we can't 
calculate anything in zero time. 

53
00:04:39,520 --> 00:04:44,539
The values just give an indication of how 
an algorithm will slow down, as n increases. 

54
00:04:44,539 --> 00:04:48,320
I'll finish this video with a comparison 
of various sorting algorithms. 

55
00:04:48,320 --> 00:04:53,200
There's a table showing how they compare, 
on the Sorting Algorithms page at Wikipedia. 

56
00:04:53,200 --> 00:04:56,890
That's quite interesting, so 
I'll switch to it in my browser. 

57
00:05:01,920 --> 00:05:04,400
We're really interested in 
the Worst column, but we'll be 

58
00:05:04,400 --> 00:05:10,802
talking about Average cases in the next video.
Quicksort and Merge sort both run in n log n, on average. 

59
00:05:10,802 --> 00:05:15,308
Merge sort wins out slightly, because 
its Worst case is still n log n. 

60
00:05:15,308 --> 00:05:21,458
Quicksort degrades to n squared in its worst case.
Where Quicksort wins out, is memory use. 

61
00:05:21,520 --> 00:05:26,560
The memory requirement of Quicksort is 
log n, which grows slowly — as we've seen. 

62
00:05:26,560 --> 00:05:31,120
The memory requirement of Merge sort is n, so 
it requires a lot more memory than Quicksort, 

63
00:05:31,120 --> 00:05:35,680
as the number of items increases.
Timsort performs better than Merge sort, 

64
00:05:35,680 --> 00:05:40,800
with a Best case of O(n). It achieves 
that when given data that's already sorted. 

65
00:05:40,800 --> 00:05:45,280
The worst case, for many sorting algorithms, 
is often when they're asked to sort data 

66
00:05:45,280 --> 00:05:50,160
that's already in order — or in reverse order.
I mention Timsort because that's the algorithm 

67
00:05:50,160 --> 00:05:56,480
that Python uses. It was created, as an 
improvement to Merge sort, by Tim Peters. 

68
00:05:56,480 --> 00:06:00,561
You may recognise his name, from some 
of the Python PEPs we've looked at. 

69
00:06:00,640 --> 00:06:04,319
He's also responsible for 
PEP 20, The Zen of Python. 

70
00:06:04,560 --> 00:06:07,760
As you can see, the order of an 
algorithm can be very useful, 

71
00:06:07,760 --> 00:06:12,400
when deciding which method to use. If 
you need to sort a large amount of data, 

72
00:06:12,400 --> 00:06:17,040
and you're interested in performance, then 
Merge sort or Timsort would be a good choice. 

73
00:06:17,040 --> 00:06:22,400
On the other hand, if you need to use memory 
carefully, the Quicksort might be a better choice. 

74
00:06:22,400 --> 00:06:26,122
You may have so little spare memory 
that you have to sacrifice performance. 

75
00:06:26,122 --> 00:06:30,480
In that case, you'd choose a sort 
that has a memory requirement of O(1). 

76
00:06:30,480 --> 00:06:34,400
Note that this refers to the memory 
used in addition to the data size. 

77
00:06:34,400 --> 00:06:38,480
The extra memory that Gnome sort uses 
is constant, whereas Timsort uses more 

78
00:06:38,480 --> 00:06:44,441
and more memory as the data size increases.
In the next video, we're going to implement a Bubble sort. 

79
00:06:44,441 --> 00:06:48,960
That has an Average and Worst case
of n squared. It's not very good, 

80
00:06:48,960 --> 00:06:52,960
but it does have the advantage of being 
very easy to write. It's often used in 

81
00:06:52,960 --> 00:06:57,659
computer science courses, to get students 
to write their first sorting function. 

82
00:06:57,659 --> 00:07:02,400
Ok, we'll finish all this theory by looking 
at average and worst cases. It's probably 

83
00:07:02,400 --> 00:07:06,400
not obvious what they refer to 
— what exactly is a Worst case? 

84
00:07:06,400 --> 00:07:11,266
We'll examine the difference, by implementing 
a Bubble sort, in the next video.