All language subtitles for 04 - Measuring Performance - Big Theta.en

af Afrikaans
ak Akan
sq Albanian
am Amharic
ar Arabic Download
hy Armenian
az Azerbaijani
eu Basque
be Belarusian
bem Bemba
bn Bengali
bh Bihari
bs Bosnian
br Breton
bg Bulgarian
km Cambodian
ca Catalan
chr Cherokee
ny Chichewa
zh-CN Chinese (Simplified)
zh-TW Chinese (Traditional)
co Corsican
hr Croatian
cs Czech
da Danish
nl Dutch
en English
eo Esperanto
et Estonian
ee Ewe
fo Faroese
tl Filipino
fi Finnish
fr French
fy Frisian
gaa Ga
gl Galician
ka Georgian
de German
el Greek
gn Guarani
gu Gujarati
ht Haitian Creole
ha Hausa
haw Hawaiian
iw Hebrew
hi Hindi
hu Hungarian
is Icelandic
ig Igbo
id Indonesian
ia Interlingua
ga Irish
it Italian
ja Japanese
jw Javanese
kn Kannada
kk Kazakh
rw Kinyarwanda
rn Kirundi
kg Kongo
ko Korean
kri Krio (Sierra Leone)
ku Kurdish
ckb Kurdish (Soranî)
ky Kyrgyz
lo Laothian
la Latin
lv Latvian
ln Lingala
lt Lithuanian
loz Lozi
lg Luganda
ach Luo
mk Macedonian
mg Malagasy
ms Malay
ml Malayalam
mt Maltese
mi Maori
mr Marathi
mfe Mauritian Creole
mo Moldavian
mn Mongolian
sr-ME Montenegrin
ne Nepali
pcm Nigerian Pidgin
nso Northern Sotho
no Norwegian
nn Norwegian (Nynorsk)
oc Occitan
or Oriya
om Oromo
ps Pashto
fa Persian
pl Polish
pt-BR Portuguese (Brazil)
pt-PT Portuguese (Portugal)
pa Punjabi
qu Quechua
ro Romanian
rm Romansh
nyn Runyakitara
ru Russian
gd Scots Gaelic
sr Serbian
sh Serbo-Croatian
st Sesotho
tn Setswana
crs Seychellois Creole
sn Shona
sd Sindhi
si Sinhalese
sk Slovak
sl Slovenian
so Somali
es Spanish
es-419 Spanish (Latin American)
su Sundanese
sw Swahili
sv Swedish
tg Tajik
ta Tamil
tt Tatar
te Telugu
th Thai
ti Tigrinya
to Tonga
lua Tshiluba
tum Tumbuka
tr Turkish
tk Turkmen
tw Twi
ug Uighur
uk Ukrainian
ur Urdu
uz Uzbek
vi Vietnamese
cy Welsh
wo Wolof
xh Xhosa
yi Yiddish
yo Yoruba
zu Zulu
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.