WEBVTT 00:00.800 --> 00:02.660 Analyzing the algorithm. 00:02.660 --> 00:09.330 So to create a good algorithm, we need to ensure that we have got the best performance from the algorithm. 00:09.350 --> 00:16.580 In this lecture, we are going to discuss the ways we can analyze the time and complexity of basing 00:16.580 --> 00:17.390 functions. 00:17.390 --> 00:20.330 So my name is Stephan and let's get started. 00:32.000 --> 00:32.750 So. 00:34.270 --> 00:37.570 Uh, we're going to start with the asymptotic analysis. 00:37.570 --> 00:42.610 So let's start with the simplistic analysis to find out the complexity of the algorithms. 00:42.610 --> 00:47.410 So this analysis omits the constants and the least significant parts. 00:47.420 --> 00:55.450 Suppose we have the function that will print a number from zero, from zero to N. 00:57.550 --> 00:59.230 We're going to create a function like this. 00:59.230 --> 01:06.280 So void, void, or actually, let's make this here, the void looping here. 01:06.280 --> 01:11.200 We're going to get an parameter which is going to be n here and we will loop through it. 01:11.200 --> 01:14.380 So integer, we're going to create a new integer E here. 01:14.380 --> 01:15.970 We're going to assign it to zero. 01:16.000 --> 01:26.440 Now we're going to create a while loop while E is less than n print on the screen with a c out E here, 01:26.440 --> 01:27.550 end line. 01:28.120 --> 01:29.170 And here. 01:29.170 --> 01:31.570 We also need to input your string here. 01:31.570 --> 01:32.110 Oops. 01:32.740 --> 01:38.150 So include and include your stream, your stream. 01:38.270 --> 01:45.290 And so we're going to print it on the screen and increment the E by one. 01:46.340 --> 01:49.700 E equals E plus one. 01:50.000 --> 01:57.830 So now let's calculate the time and complexity of the preceding algorithm by counting the each instruction 01:57.830 --> 01:59.600 of the function here. 02:00.040 --> 02:07.450 So this statement is only executed once in the function, so its value is one. 02:07.450 --> 02:14.050 So this code snippet here of the of the rest statements in the looping function. 02:14.050 --> 02:18.280 So the comparison while loop is valued at one. 02:18.280 --> 02:25.390 And for simplicity we can say that the value of the two statements inside the while loop scope is three 02:25.420 --> 02:25.960 signs. 02:25.960 --> 02:35.590 It needs one to print the variable and two for assignment and addition here. 02:35.710 --> 02:42.970 So however, how much of the this code is executed depends on the value of N here. 02:43.150 --> 02:45.520 So it will be one here. 02:45.850 --> 02:59.870 Let's actually make our mathematical here so it will be one plus three and multiply by N or for n here. 02:59.870 --> 03:01.850 You can also do it like that. 03:01.850 --> 03:04.250 So the total instruction. 03:06.010 --> 03:13.480 Uh, that has to be executed for this looping function is one plus four. 03:13.480 --> 03:19.670 N Therefore, the complexity of this looping function is here. 03:19.690 --> 03:22.420 So the time complexity here. 03:23.150 --> 03:24.020 The time. 03:24.020 --> 03:25.070 Complexity. 03:25.100 --> 03:25.940 Time. 03:25.940 --> 03:27.200 Complexity. 03:27.260 --> 03:27.770 Yeah. 03:27.800 --> 03:28.490 Time. 03:28.490 --> 03:29.570 Complexity. 03:32.200 --> 03:34.590 And here time comes complexity. 03:34.600 --> 03:38.650 N is equals for. 03:39.360 --> 03:41.970 And plus one here. 03:41.970 --> 03:45.570 So and there is let's actually create our curve here. 03:45.570 --> 03:47.240 So in this case, it's our curve. 03:47.250 --> 03:55.020 For example, let's just create a score here and this is our way, this goes here. 03:55.590 --> 04:00.360 So it will be for N plus. 04:01.280 --> 04:01.970 One. 04:03.660 --> 04:13.050 So in our core graphics that will be represented in this course, the here, let's actually create this 04:13.080 --> 04:13.890 again. 04:17.270 --> 04:21.510 And this goes from here to here. 04:21.530 --> 04:25.850 So for n plus one. 04:27.790 --> 04:30.040 So this is the input axis. 04:30.040 --> 04:39.940 The x axis here represent the input size N and the U here, the x axis here. 04:40.260 --> 04:42.000 Let's actually write in red. 04:42.010 --> 04:46.030 This is U here and this is X here. 04:46.270 --> 04:53.430 So this axis here represents the execution time. 04:53.440 --> 04:55.570 So here this means here. 04:55.570 --> 04:58.630 This is the time. 05:00.050 --> 05:04.580 So as you can see in this graphic, the curve is linear. 05:04.580 --> 05:10.820 However, since the complexity is also depends on the other parameters such as hardware specification, 05:10.820 --> 05:17.300 we may have another complexity for the preceding looping function if we run the function on a faster 05:17.300 --> 05:18.050 hardware. 05:18.050 --> 05:31.130 So let's say that complexity becomes two N, let's actually here, yeah, two N plus 0.5 so that the 05:31.130 --> 05:34.520 curve curve will be like this. 05:34.520 --> 05:41.510 So for example, this was the previous curve and this is the this is going to be our next curve here. 05:41.510 --> 05:42.530 It's going to be like this. 05:42.530 --> 05:53.330 So this is the four plus four N plus one, and this is the two N plus 0.5 here. 05:53.330 --> 05:59.480 So it will be go down the time complexity if we have higher, faster hardware. 05:59.480 --> 06:04.260 So as you can see, the curve is still linear for the two complexities. 06:04.260 --> 06:09.990 For this reason, we can omit a constant and the least significant part is asymptotic analysis. 06:09.990 --> 06:16.500 So we can say that this complexity is n here. 06:16.500 --> 06:21.360 For example, the time complexity n here is equals to n. 06:24.510 --> 06:25.110 Here. 06:25.560 --> 06:27.870 So let's move another function. 06:28.950 --> 06:30.450 If we have nested while loop. 06:30.450 --> 06:32.460 So we will have another complexity here. 06:32.460 --> 06:34.860 So looping while and void. 06:36.230 --> 06:38.570 This is going to be my pairing here. 06:38.600 --> 06:41.540 Pair pairing here. 06:41.540 --> 06:50.810 And it's going to also get the integer n and we will create a new value named integer E here zero while 06:50.840 --> 06:53.810 the e is less than n. 06:54.820 --> 06:55.810 Then we're going to. 06:56.850 --> 06:57.860 Could a new value. 06:58.140 --> 07:01.140 The integer g here is zero. 07:01.320 --> 07:09.720 And while the g g is less than n, we will print this on the screen. 07:09.720 --> 07:12.180 So see out E here. 07:14.840 --> 07:19.100 And also here and in line and line. 07:19.670 --> 07:22.460 After that, we will equal G. 07:22.550 --> 07:24.470 Equals G plus one. 07:24.470 --> 07:31.310 And outside the our nested while loop in the first while loop here inside the first while loop we're 07:31.310 --> 07:34.340 going to equal E equals e plus one. 07:34.370 --> 07:35.390 E plus one. 07:35.960 --> 07:36.190 Yeah. 07:36.320 --> 07:43.250 So based on the looping function here, we can say that the complexity of the inner while loop of this 07:43.250 --> 07:48.650 parent function is for n plus one. 07:48.650 --> 07:50.840 So we then calculate the while loop. 07:50.840 --> 07:55.730 So it becomes uh, here, uh, let's actually make this like that. 07:57.760 --> 08:00.010 The one plus. 08:00.720 --> 08:07.500 And multiply by four n plus one and plus two. 08:07.740 --> 08:17.550 So which equals to one plus three N plus four N square here. 08:19.230 --> 08:20.100 Square. 08:20.400 --> 08:27.180 So therefore, the complexity of this preceding code is this. 08:28.130 --> 08:30.260 Time complexity is going to be. 08:32.590 --> 08:35.140 Here in this, as you can see here. 08:35.140 --> 08:44.380 So here the time complexity instead of for n plus one, we're going to have the for the time complex 08:44.380 --> 08:52.150 is going to be for n square here for n square plus three n plus one. 08:54.190 --> 08:59.620 So and the curve of this preceding flow is going to be like this here. 08:59.650 --> 09:07.810 This is our curve and it's going to be go from here and update like this. 09:07.870 --> 09:08.040 Oops. 09:08.050 --> 09:10.470 Actually, let's make the different color here. 09:10.480 --> 09:12.490 Go from here and update like this. 09:12.670 --> 09:24.010 So here, this is going to be for n for n two plus three, N plus one, and it's going to be this is 09:24.010 --> 09:27.020 the time and this is the complexity here. 09:27.040 --> 09:35.350 So and if the run if we run this code in the higher software, the complexity might become twice as 09:35.350 --> 09:35.620 slow. 09:35.620 --> 09:39.910 So and the notation is going to be, for example. 09:41.520 --> 09:43.220 Eight and square. 09:43.540 --> 09:44.310 Eight. 09:45.510 --> 09:50.220 Yeah, the notation is going to be eight and square here. 09:52.600 --> 09:54.910 Plus six and plus two. 09:54.940 --> 09:56.890 It's conversation is going to be like this. 09:57.700 --> 10:02.710 And the curve of notation is gonna like this. 10:02.710 --> 10:13.750 So, for example, let's say this is our previous curve and this is going to be our next curve here 10:13.750 --> 10:14.560 like this. 10:15.040 --> 10:22.150 And this is going to eight N square plus six and that we've written here plus two here. 10:22.150 --> 10:22.810 So. 10:23.710 --> 10:30.730 And as shown here, signs the asymptotic analysis omits the constant and the least significant parts. 10:30.760 --> 10:37.420 The complexity of the notation will be n two of our time complexity.