Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
0
00:00:01,867 --> 00:00:08,867
Recall the method from before that just loops through N numbers and writes the current number to the console.
1
00:00:08,867 --> 00:00:15,867
As you might remember, we estimated it to consume 4N + 1 instructions given an input parameter N.
2
00:00:15,867 --> 00:00:23,867
Here I have named that expression f of N and drawn it in the graph to the left for various values of N.
3
00:00:23,867 --> 00:00:30,867
Without any reason, at least for now, I'll introduce another function and name it g of N.
4
00:00:30,867 --> 00:00:42,866
I define g of N as just N. Now, I can come up with a number, say 3, and multiply g of N with that number.
5
00:00:42,866 --> 00:00:54,866
Here is the corresponding graph. And as you can see, the first function, f of N, stays above 3g of N everywhere.
6
00:00:54,866 --> 00:01:01,866
Similarly, I can come up with another number, say, 5, and multiply g of N with that.
7
00:01:01,866 --> 00:01:10,867
Here is the corresponding graph. As you can see, f stays under 5g of N.
8
00:01:10,867 --> 00:01:15,867
So we now have two boundaries for f, a lower bound and an upper bound.
9
00:01:15,867 --> 00:01:22,867
This means that if stays within the gray area, and is squeezed in between the two boundaries.
10
00:01:22,867 --> 00:01:29,867
Notice that the only difference between the upper bound and the lower bound is the constants that g of N is multiplied with.
11
00:01:29,867 --> 00:01:39,867
And therefore, the curve of our real execution complexity, f, is of the same nature as the curve described by g.
12
00:01:39,867 --> 00:01:46,867
This may require some thoughts, but remember that running a given program on slow and fast hardware will
13
00:01:46,867 --> 00:01:53,867
result in the same kind of curve if we draw the execution time for various sizes of input.
14
00:01:53,867 --> 00:02:02,867
The only difference is some constant factor. Thus, if we can bound the real execution time within the two
15
00:02:02,867 --> 00:02:11,866
constant factors of a certain curve, we can use that curve to describe the behavior of the complexity of our program.
16
00:02:11,866 --> 00:02:19,866
In this case, we could use g of N to describe the complexity of f of N.
17
00:02:19,866 --> 00:02:28,866
Another way to write this is to say that f is Big Theta of g of N.
18
00:02:28,866 --> 00:02:38,866
That is, f is Big Theta of N, since g of N was just N. As an example of a curve that is not Big Theta of N,
19
00:02:38,866 --> 00:02:47,866
that is, a curve that cannot be bounded by g of N multiplied with some constant factors, take a look at this curve.
20
00:02:47,866 --> 00:02:54,866
Let's consider another example. Recall this example from before that has two nested loops and produces all
21
00:02:54,866 --> 00:03:01,866
pairs of integers between 0 and N, or N - 1 to be precise.
22
00:03:01,866 --> 00:03:07,866
Let's take a look at some graphs. As you might remember, we calculated the complexity as I have written on
23
00:03:07,866 --> 00:03:13,866
the screen here, and as you can see, this is not a straight line.
24
00:03:13,866 --> 00:03:22,866
Again, I have named the expression f of N. Let's try to see if we can bound that function to like we did before.
25
00:03:22,866 --> 00:03:30,866
I introduced a new function, g of N, which I set to the most significant component in f of N, namely N squared.
26
00:03:30,866 --> 00:03:41,866
Similarly as before, I can use a constant factor, say, 3, and multiply g of N with 3 to obtain a lower bound for f.
27
00:03:41,866 --> 00:03:51,866
Also, I can use the constant factor 5 to obtain an upper bound of f, namely 5g of N.
28
00:03:51,866 --> 00:03:59,866
Here is a graph, and notice that f stays under 5g of N for almost all values of N.
29
00:03:59,866 --> 00:04:08,866
To see why I say almost all, consider this table. The table contains the first four values of N,
30
00:04:08,866 --> 00:04:17,867
and the corresponding values of f of N. Here are the values of 5g of N, and as you can see, 5g of N is
31
00:04:17,867 --> 00:04:31,867
actually smaller than f of N until N is 4. So, 5g of N is only an upper bound after N is strictly larger than 3.
32
00:04:31,867 --> 00:04:38,867
We can now write that f of N is squeezed in between g of N multiplied with a low and a high number
33
00:04:38,867 --> 00:04:47,867
respectively, when N is strictly larger than 3. We had a shorter way to write this, as you remember from
34
00:04:47,867 --> 00:04:55,867
the previous example, namely that f is Big Theta of g of N, and since g of N equals N squared, we can also
35
00:04:55,867 --> 00:05:05,867
write this as Big Theta of N squared. An example of a curve that is not Big Theta of N squared is the line from before.
36
00:05:05,867 --> 00:05:12,867
That line was Big Theta of N and grows much slower, as you can see.
37
00:05:12,867 --> 00:05:18,867
Okay, time to be a bit more explicit about this Big Theta. What is it exactly?
38
00:05:18,867 --> 00:05:25,867
So consider a function f. I have put the function from the previous example up as an example in the gray box.
39
00:05:25,867 --> 00:05:33,867
We then need three things to exist in order for f to be Big Theta of some other function g of N.
40
00:05:33,867 --> 00:05:38,867
First of all, we need some function g of N in the first place, and as you can see, a good candidate for g of
41
00:05:38,867 --> 00:05:47,867
N is the element from f of N with the highest order. In the examples in the gray boxes, it's N squared.
42
00:05:47,867 --> 00:05:54,867
Next, we need two constants. Here I have called them c1 and c2, and in the examples from before,
43
00:05:54,867 --> 00:06:04,867
these have the values 3 and 5, respectively. We also need a third constant, say, small n.
44
00:06:04,867 --> 00:06:11,867
In the example, small n was the constant 3 that capital N had to be strictly larger than before the
45
00:06:11,867 --> 00:06:22,867
boundaries were actually boundaries. So, if f can be squeezed in between c1 times g of N and C2 times g of N,
46
00:06:22,867 --> 00:06:30,867
whenever capital N is strictly larger than small n, then we say that f is Big Theta of g of N,
47
00:06:30,867 --> 00:06:40,867
and typically we just write whatever g of N is. In the previous example, we just wrote Big Theta of N squared.
48
00:06:40,867 --> 00:06:48,867
We use Big Theta to express complexity, but how do we express that something takes constant time, that is,
49
00:06:48,867 --> 00:06:55,867
the same amount of time independently of the input size n? Let's say that a part of a program uses,
50
00:06:55,867 --> 00:07:02,867
for example, 19 instructions independently of n. We can use the same principles as before, so introduce a
51
00:07:02,867 --> 00:07:16,867
function g of N and set it to 1, just the constant 1. Now introduce a constant factor, say, 18.999 and
52
00:07:16,867 --> 00:07:27,867
scale g of N with that. So now I have a lower bound. Also, introduce another constant factor, say, 19.0001,
53
00:07:27,867 --> 00:07:38,867
and scale g of N with that to get an upper bound. So now we can use g of N to express the complexity in Big Theta notation.
54
00:07:38,867 --> 00:07:47,867
In other words, if is Big Theta of 1. This will actually be the case no matter what constant value that f would have.
55
00:07:47,867 --> 00:07:55,867
So in order to describe that something is constant, we can say that it is Big Theta of 1.
56
00:07:55,867 --> 00:08:00,867
I've just spent the last couple of minutes to convince you that looking at the nature of the curve would
57
00:08:00,867 --> 00:08:08,867
give you the true picture of the performance. In general that is also true, but you should be aware of the caveats.
58
00:08:08,867 --> 00:08:14,867
Assume that some program has the performance characteristics of Big Theta of N.
59
00:08:14,867 --> 00:08:21,867
This is a straight line, and generally this means that it scales well and the execution time does not explode
60
00:08:21,867 --> 00:08:29,867
for last values of N. Compare that to performance characteristics of big theta of N squared.
61
00:08:29,867 --> 00:08:34,866
This is a curve that grows quickly, and generally this is a bad sign.
62
00:08:34,866 --> 00:08:38,866
However, assume that the constant factors that we need to bound the re-performance as is written on the
63
00:08:38,866 --> 00:08:46,866
screen here, very large numbers for the linear function, and very small numbers for the quadratic function.
64
00:08:46,866 --> 00:08:52,866
This means that the program with the linear performance still uses a very high number of instructions
65
00:08:52,866 --> 00:08:59,866
compared to the program with the quadratic characteristics. In fact, if these are the constants needed to
66
00:08:59,866 --> 00:09:09,866
bound the actual performance of the two programs, the quadratic performing program will win until N is larger than 900.
67
00:09:09,866 --> 00:09:15,866
It will, however, grow at an increasing rate and it will catch up on the linear function, that is,
68
00:09:15,866 --> 00:09:23,866
the Big Theta concept is true for larger values for N, but for N smaller than 900 in this example,
69
00:09:23,866 --> 00:09:29,866
the linearly performing program will be slower for this specific example, and maybe that's good enough if we
70
00:09:29,866 --> 00:09:36,000
only need to run our program for such small inputs.
9459
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.