Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
1
00:00:07,801 --> 00:00:14,801
We used the example code shown here, and as you can see, the program execution speed will be pretty
2
00:00:14,801 --> 00:00:23,800
predictable and consistent given the input N. The execution time is consistently linear in the input N.
3
00:00:23,800 --> 00:00:30,800
Here you see another example of a method, ContainsNeedle, that takes an integer, our needle, and a list of
4
00:00:30,800 --> 00:00:37,801
integers, our haystack. The function compares all entries in the haystack with the needle, and in the case
5
00:00:37,801 --> 00:00:45,801
of a match, it returns true. In case of no match, it returns false.
6
00:00:45,801 --> 00:00:51,801
In this example, the execution time depends on where the needle is positioned in the haystack,
7
00:00:51,801 --> 00:00:58,801
if it's present at all. If the needle is found at the first element, then the function returns immediately,
8
00:00:58,801 --> 00:01:07,801
and have a complexity of Big Theta of 1. Otherwise, it may scan through the whole haystack, and if the
9
00:01:07,801 --> 00:01:13,801
haystack has N elements, then the complexity will be Big Theta of N.
10
00:01:13,801 --> 00:01:19,801
So the exact complexity depends on the actual input contents, and therefore it makes sense to talk about the
11
00:01:19,801 --> 00:01:28,801
worst-case complexity of the program. And this is exactly what the Big O notation is all about.
12
00:01:28,801 --> 00:01:36,801
Let's take a close look at this ContainsNeedle method. If the haystack contains N elements, then for each
13
00:01:36,801 --> 00:01:48,801
loop will iterate through at most N elements. In each iteration it performs exactly one comparison.
14
00:01:48,801 --> 00:01:52,801
And whenever it returns, we can say that it uses one instruction.
15
00:01:52,801 --> 00:02:01,801
In total, we get N times 1, + 1 instructions, or just N + 1.
16
00:02:01,801 --> 00:02:08,800
Let's denote that f of N. If we draw it on a graph, it looks like this.
17
00:02:08,800 --> 00:02:15,800
And just like with the Big Theta notation, I now introduce another function g of N, which I set to the
18
00:02:15,800 --> 00:02:25,800
most significant component in f, namely N. Now I use the constant factor, 1.5, to create an upper bound for
19
00:02:25,800 --> 00:02:37,800
f, namely 1.5 g of N. As you can see, f stays under 1.5 g of N, but only when N is at least 2.
20
00:02:37,800 --> 00:02:48,800
This is exactly what is needed for being Big O of g of N, that is, for f being Big O of N.
21
00:02:48,800 --> 00:02:50,800
Let's formalize this a bit.
22
00:02:50,800 --> 00:02:57,800
You may recognize large parts of this from the previous slide. So consider the actual complexity for our
23
00:02:57,800 --> 00:03:05,800
program and denote that with f of N. Again, we need three things to exist.
24
00:03:05,800 --> 00:03:15,800
The function that we will use as bound, let's denote it g of N, we need a single constant, say c.
25
00:03:15,800 --> 00:03:23,800
Notice that in Big Theta we needed two constants for an upper and lower bound respectively, but now we only need one.
26
00:03:23,800 --> 00:03:30,800
And last, we need the same kind of constant factor as in Big Theta, namely small n.
27
00:03:30,800 --> 00:03:41,800
If we can bound f below c times g of N, whenever the input size is larger than small n, then f is set to be
28
00:03:41,800 --> 00:03:51,800
Big O of g of N, and again, we normally just write whatever go of N actually is instead of writing g of N explicitly.
29
00:03:51,800 --> 00:04:00,800
Recall the ContainsNeedle function, and assume that this is a representation of our haystack.
30
00:04:00,800 --> 00:04:09,800
Also assume that the needle to find is 26. The ContainsNeedle method, as we saw, iterates through all
31
00:04:09,800 --> 00:04:16,800
elements in the haystack to find the needle. If the haystack contains 10 elements, this requires 10
32
00:04:16,800 --> 00:04:25,800
comparisons worst case, and if the haystack contains 1 million elements, it requires 1 million comparisons worst case.
33
00:04:25,800 --> 00:04:32,800
If there is N elements in the haystack, then the worst-case complexity was O of N as you might remember.
34
00:04:32,800 --> 00:04:40,800
There is a smarter way of performing the search, however. If we know in advance that the haystack is ordered
35
00:04:40,800 --> 00:04:45,800
with the smallest element in the beginning and the largest element at the end.
36
00:04:45,800 --> 00:04:51,800
We can do this ordering fast, by the way, and we'll get to that in the module about algorithms, but for now,
37
00:04:51,800 --> 00:05:00,800
just assume that the haystack is ordered perhaps by magic. First, consider the middle element in the haystack.
38
00:05:00,800 --> 00:05:10,800
In this case, this has the value 20. The needle is larger than 20, so we can from now on safely ignore all
39
00:05:10,800 --> 00:05:15,800
elements to the left, because we know that the haystack is ordered.
40
00:05:15,800 --> 00:05:24,800
In the remaining part, we find the middle element again. This has the value 30; 26 is smaller than 30,
41
00:05:24,800 --> 00:05:32,800
so we can from now on safely ignore all elements to the right. We are quickly eating up the list, as you can see.
42
00:05:32,800 --> 00:05:39,800
In the remaining list we find the middle element again, and this has the value of 25, which is smaller than
43
00:05:39,800 --> 00:05:47,800
26, and therefore we ignore all the elements to the left. In the remaining list, which is now only one
44
00:05:47,800 --> 00:05:56,800
single element wide, we find the middle element, which is trivial, and we find our needle.
45
00:05:56,800 --> 00:06:03,800
So, how many comparisons is needed worst case to find the needle using this strategy?
46
00:06:03,800 --> 00:06:09,800
That is the number of times we can cut the haystack in half until we reach a size of one.
47
00:06:09,800 --> 00:06:15,800
But how many times is that? Let's spend a moment talking about
48
00:06:15,800 --> 00:06:26,800
logarithms and return to our binary search in a short while. So, consider the product 2 times 2 times 2 and
49
00:06:26,800 --> 00:06:36,800
so on 7 times. Another way to write this is 2 to the power of 7. This is 128, by the way.
50
00:06:36,800 --> 00:06:46,800
If we multiply with 2 one more time, we get 2 to the power of 8, which is 256.
51
00:06:46,800 --> 00:06:58,500
And one more 2 gives 2 to the power of 9, which in turn is 512. In general, if we have 2 times 2 times 2 and
52
00:06:58,500 --> 00:07:06,800
so on, N times, we write it 2 to the power of N, and call it an exponential function.
53
00:07:06,800 --> 00:07:15,800
It looks like this. And if you take a look at the values of the axes, you can see that it grows extremely fast.
54
00:07:15,800 --> 00:07:26,800
Now we could ask what should N be in order for 2 to the power of N to give, for example, 4096?
55
00:07:26,800 --> 00:07:31,500
There is a mathematical function that gives the answer to this question, and that is called the logarithm.
56
00:07:31,500 --> 00:07:42,000
It is written like this. The subscript 2 is called the logarithm base and refers to the 2 from the exponential function.
57
00:07:42,000 --> 00:07:49,000
Another kind of logarithm, say with base 10, refers to the exponential function 10 to the power of N and
58
00:07:49,000 --> 00:07:56,500
answers what N should be in order for 10 to the power of N to be something.
59
00:07:56,500 --> 00:08:03,000
But when talking algorithms and data structures, we typically use logarithms with base 2.
60
00:08:03,000 --> 00:08:14,000
To answer the questions, the logarithm of 4096 is 12, because 2 to the power of 12 is 4096.
61
00:08:14,000 --> 00:08:21,000
Here's a graph showing the logarithm of N, or sometimes just referred to as log N.
62
00:08:21,000 --> 00:08:27,000
If you consider the values of the axes, you can see that the function grows very slowly.
63
00:08:27,000 --> 00:08:33,000
In fact, it grows slower and slower for higher values of N.
64
00:08:33,000 --> 00:08:43,000
Consider this tree displaying a series of doublings starting from 1 and ending at 16 after 4 doublings.
65
00:08:43,000 --> 00:08:50,000
If we go upwards instead and look at the number of halvings of 16 before we get to 1, that number is the
66
00:08:50,000 --> 00:08:57,500
logarithm of 16, which in turn gives 4. Let's head back to our binary search.
67
00:08:57,500 --> 00:09:04,000
We left where we needed the number of halvings of N, and now we have the answer.
68
00:09:04,000 --> 00:09:12,000
This is exactly the logarithm of N. So the total complexity of our binary search is something with logarithm
69
00:09:12,000 --> 00:09:20,000
of N, because this was a number of comparisons, and for each comparison, we need to perform something,
70
00:09:20,000 --> 00:09:27,000
which takes a number of instructions. The thing is that the exact number of instructions is actually not
71
00:09:27,000 --> 00:09:33,000
that important, as long as we know that it is the same number of instructions each time.
72
00:09:33,000 --> 00:09:40,000
In other words, that it is constant. I therefore just write c as a representation of any constant number,
73
00:09:40,000 --> 00:09:49,000
so now that I have written c times log N as a total worst-case complexity, I can easily create an upper
74
00:09:49,000 --> 00:09:57,000
bound for that expression, namely by using any larger constant, for example, c + 1.
75
00:09:57,000 --> 00:10:06,000
Since this log N must multiplied with a larger constant is an upper bound, I can now write that our
76
00:10:06,000 --> 00:10:14,000
complexity is Big O of log N. And this is a great worst-case guarantee.
77
00:10:14,000 --> 00:10:23,000
For instance, it only takes 14 comparisons to find a needle among 10,000 entries, and only 6 comparisons more
78
00:10:23,000 --> 00:10:27,000
to find a needle among 1,000,000 entries.
79
00:10:27,000 --> 00:10:35,000
So, a few points about the Big O notation. One could argue that finding an upper bound is easy, it is just
80
00:10:35,000 --> 00:10:44,000
to use some extremely fast-growing function, for example, 999 to the power of N, which grows faster than
81
00:10:44,000 --> 00:10:50,000
almost all of our functions. But the worst-case guarantee should be relevant.
82
00:10:50,000 --> 00:10:56,000
Consider this graph over some data. It could be the stock market the last hour.
83
00:10:56,000 --> 00:11:02,000
Then it's certainly true that the green line is an upper bound to the graph, but just as you do not get much
84
00:11:02,000 --> 00:11:10,000
information if I tell you that my car drives at most 10 billion km per hour, that green line does not provide
85
00:11:10,000 --> 00:11:19,000
much information as well. The upper bound is most useful if it is related to the actual worst case scenario.
86
00:11:19,000 --> 00:11:24,000
In general, we should try to find the lowest possible worst-case.
87
00:11:24,000 --> 00:11:36,000
As an example, it is true that N squared + N is Big O of N to the power of 3, but Big O of N squared is more interesting.
88
00:11:36,000 --> 00:11:41,000
And in general, we searched for a so-called tight bound.
11283
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.