WEBVTT 00:00.490 --> 00:07.720 In previous lecture, we were able to define the time complexity for our code using the asymptotic algorithm. 00:07.810 --> 00:14.500 In this section or in this lecture, we are going to determine a case of the implementation of an algorithm. 00:14.500 --> 00:22.780 So there are three cases when implementing the complexity of algorithm is the there are the worse here 00:22.780 --> 00:25.090 actually lets me fix that here. 00:25.090 --> 00:27.160 So there are the worst. 00:29.570 --> 00:31.100 The average. 00:35.270 --> 00:36.830 And best. 00:39.440 --> 00:45.660 So before we go through them, let's look at the search function implementation here. 00:45.680 --> 00:49.250 So now we're going to create the new search function here. 00:49.280 --> 00:51.920 Integer search. 00:52.430 --> 00:57.620 And that's going to take the parameter integer array here and integer. 00:57.650 --> 00:59.510 Integer array. 00:59.510 --> 01:02.960 Size and integer X. 01:04.310 --> 01:06.230 So here we will. 01:06.350 --> 01:10.190 After that we will create a for loop to iterate through the array elements. 01:10.190 --> 01:17.510 So integer E equals zero while the E is less than array size. 01:19.390 --> 01:20.650 And E plus. 01:20.650 --> 01:21.190 Plus. 01:21.220 --> 01:21.940 Or plus. 01:21.940 --> 01:22.390 Plus E. 01:23.290 --> 01:23.530 Okay. 01:23.560 --> 01:24.250 Correct. 01:24.460 --> 01:29.530 And here, uh, the if our x here. 01:29.530 --> 01:35.210 If our x is found, return the index index of x here. 01:35.230 --> 01:47.110 So if our array dot e here is equals to x, then return E here. 01:47.140 --> 01:51.190 This means we found our, uh, searching element here. 01:51.190 --> 01:54.610 So if our x x is not found here. 01:54.610 --> 02:02.590 So if, uh, this loop, this condition is not executed, this means our X is not found here. 02:02.590 --> 02:07.060 So now we're going to create here this, uh, consider this as an else statement here. 02:07.060 --> 02:17.110 So if X is not found, then return, uh, if we then return or not here to be correct. 02:17.350 --> 02:21.860 If x is not found, then return the minus one. 02:22.010 --> 02:23.960 Return minus one here. 02:24.770 --> 02:31.400 As you can see here, this search function, it will find an index of target element. 02:31.580 --> 02:42.860 This is here X from an array, a a r r array containing a R size elements. 02:42.860 --> 02:45.650 So suppose we have the array of here. 02:45.680 --> 02:49.760 Let's actually create the 4255 and. 02:51.630 --> 02:53.700 Let's actually create our array here. 02:54.180 --> 02:57.270 So integer array. 03:00.290 --> 03:00.890 Here. 03:01.520 --> 03:05.580 So let's create our array here with five. 03:06.820 --> 03:07.900 Thanks for. 03:18.320 --> 03:19.970 Here is our array. 03:21.680 --> 03:26.210 And we will make this for example, our array size is going to be nine. 03:26.210 --> 03:34.970 So search, search, our array is going to be R, the array size is going to be nine. 03:35.000 --> 03:36.560 Oops, uh, nine. 03:36.560 --> 03:42.230 And what we want to find is, for example, 97. 03:43.580 --> 03:44.240 Here. 03:46.520 --> 03:47.930 If we run this program. 03:49.670 --> 03:54.920 Here we have no output, but we are code is compiled without an error. 03:54.920 --> 03:57.350 So we have the worst case. 03:57.380 --> 03:59.570 Let's actually start with the learning about the worst case. 03:59.570 --> 04:02.290 Actually, let's first print our here. 04:02.300 --> 04:11.060 So c out here, then print the array dot e here and make this. 04:14.180 --> 04:20.630 Found and re here and after that end line. 04:24.130 --> 04:25.630 And see out. 04:26.850 --> 04:28.830 Element not found. 04:30.500 --> 04:32.720 And new line and line. 04:33.770 --> 04:35.660 Let's run it again. 04:36.330 --> 04:39.040 And as you can see here, we found our array. 04:39.060 --> 04:43.650 So let's 22 and as you can see, we have no 22 in this array. 04:43.650 --> 04:49.890 And as you can see, we got an A finished with exit code because element is not found here. 04:51.400 --> 04:55.460 So let's get started with the worst case analysis. 04:55.480 --> 04:58.820 Average case analysis and best case analysis here. 04:58.840 --> 05:05.890 So worst case analysis is a calculation of the upper bound on the running runtime or of the running 05:05.920 --> 05:06.940 time of the algorithm. 05:06.940 --> 05:09.610 So in the search function. 05:09.940 --> 05:17.050 The upper bound can be an element that does not appear in the IRR. 05:17.440 --> 05:19.840 For instance, here 60. 05:19.990 --> 05:27.580 So it has to iterate through all elements of array IRR variable and still cannot find the element. 05:27.590 --> 05:30.310 So this is our worst. 05:32.080 --> 05:32.950 Case. 05:33.070 --> 05:35.710 We also have the average case here. 05:35.740 --> 05:36.790 Average. 05:37.770 --> 05:38.400 Case. 05:38.550 --> 05:45.090 So average case analysis is a calculation of all possible inputs on the running time of algorithm, 05:45.090 --> 05:49.890 so including an element that is not present in the arrays. 05:49.920 --> 05:53.340 We also have the best case. 05:54.000 --> 05:55.230 The best. 05:56.070 --> 06:02.100 Best case analysis is a calculation of the lower bound on the running time of the algorithm. 06:02.100 --> 06:07.770 So in the search function, the lower bound is the first element of the array, which is 45. 06:07.800 --> 06:15.060 So when we search for element 45, the function will only iterate through R only once. 06:15.060 --> 06:19.770 So the array size doesn't matter here. 06:27.460 --> 06:31.210 You can also do it like that and element not found. 06:32.800 --> 06:35.860 And continuing iterating. 06:36.100 --> 06:38.080 Element not found and iterating. 06:39.850 --> 06:40.210 Here. 06:41.910 --> 06:42.820 Run it again. 06:43.060 --> 06:48.730 And as you can see here, our element not found either here. 06:49.290 --> 06:51.270 That was the worst case scenario. 06:52.210 --> 07:00.730 The worst case scenario is whenever we found out, for example, 25, 21 or 14 here if we have 14. 07:02.180 --> 07:05.150 Of the race as it's going to be nine here. 07:05.420 --> 07:09.620 Our X here is going to be 14, for example. 07:11.290 --> 07:18.250 And as you can see here, after the iterating, one, two, three, four, five, six, seven, eight, 07:18.280 --> 07:22.090 nine, the 14 is found.