1
00:00:05,120 --> 00:00:10,160
You may have come across the term Big O, when 
looking at different algorithms. In this section, 

2
00:00:10,160 --> 00:00:14,880
I'll explain what it is and why it's useful.
I'll also be explaining what it's not.

3
00:00:14,880 --> 00:00:19,600
In particular, it doesn't guarantee that one 
algorithm will execute faster than another. 

4
00:00:19,600 --> 00:00:22,720
It's basically a way to talk about 
the complexity of an algorithm, 

5
00:00:22,720 --> 00:00:26,957
or the complexity of 
operations on a data structure. 

6
00:00:28,400 --> 00:00:33,760
What I certainly won't be doing, is providing 
a rigorous, mathematical discussion of Big O. 

7
00:00:33,760 --> 00:00:37,440
There's a good reason why I won't be 
doing that — the maths gets horrible. 

8
00:00:37,440 --> 00:00:40,160
When we looked at the Wikipedia 
entry for Hash functions, 

9
00:00:40,160 --> 00:00:44,720
back in the Dictionaries and sets section, 
there was some pretty scary maths in there. 

10
00:00:44,720 --> 00:00:47,360
I encouraged you to skim through 
the article, because there were 

11
00:00:47,360 --> 00:00:51,833
some interesting points that you could get 
from it, without worrying about the maths. 

12
00:00:53,040 --> 00:00:56,800
Let's have a quick look at the 
Wikipedia article about Big O notation. 

13
00:00:56,800 --> 00:01:00,000
I'll open that page in my browser. 

14
00:01:03,120 --> 00:01:08,759
I don't suggest you read this, unless you're a 
mathematician, in which case it might make sense. 

15
00:01:08,759 --> 00:01:12,000
For the rest of us, the only thing 
that will probably make sense, 

16
00:01:12,000 --> 00:01:17,520
is the first sentence of the second paragraph:
"In computer science, big O notation is used 

17
00:01:17,520 --> 00:01:21,280
to classify algorithms according to how 
their run time or space requirements grow, 

18
00:01:21,280 --> 00:01:25,640
as the input size grows."
That's not too complicated. 

19
00:01:25,640 --> 00:01:31,948
We use big O notation to indicate how much longer an 
algorithm will take, as we give it larger values to work on. 

20
00:01:31,948 --> 00:01:36,329
Another way to think of that is, 
how many operations the algorithm has to perform. 

21
00:01:36,400 --> 00:01:39,600
That sentence also talked 
about space requirements. 

22
00:01:39,600 --> 00:01:44,560
We can use big O to talk about how much 
memory is needed, or how much disk space. 

23
00:01:44,560 --> 00:01:48,880
That's the only sentence I suggest you 
read — unless you are a mathematician. 

24
00:01:48,880 --> 00:01:54,000
The article opens by talking about "mathematical 
notation", and "limiting behaviour", and "tending 

25
00:01:54,000 --> 00:01:59,200
towards infinity". If that wasn't bad enough, 
you don't have to scroll very far down, to see 

26
00:01:59,200 --> 00:02:05,000
some really confusing formulae. Scroll until 
Formal Definition is at the top of your screen. 

27
00:02:05,200 --> 00:02:09,579
That's horrible, and it only gets 
worse, the further you scroll down. 

28
00:02:10,720 --> 00:02:14,000
The good news is, we don't have to understand all this. 

29
00:02:14,000 --> 00:02:17,600
I'll summarise Big O notation with some slides.

30
00:02:18,364 --> 00:02:24,254
Big O notation is used to describe how the running time
(or space requirements) of an algorithm grows,

31
00:02:24,254 --> 00:02:27,260
as you give it larger data sets to process.

32
00:02:27,260 --> 00:02:32,369
Programmers commonly use big O notation, rather 
than the other notations that are also available.