1 00:00:00,490 --> 00:00:07,720 In previous lecture, we were able to define the time complexity for our code using the asymptotic algorithm. 2 00:00:07,810 --> 00:00:14,500 In this section or in this lecture, we are going to determine a case of the implementation of an algorithm. 3 00:00:14,500 --> 00:00:22,780 So there are three cases when implementing the complexity of algorithm is the there are the worse here 4 00:00:22,780 --> 00:00:25,090 actually lets me fix that here. 5 00:00:25,090 --> 00:00:27,160 So there are the worst. 6 00:00:29,570 --> 00:00:31,100 The average. 7 00:00:35,270 --> 00:00:36,830 And best. 8 00:00:39,440 --> 00:00:45,660 So before we go through them, let's look at the search function implementation here. 9 00:00:45,680 --> 00:00:49,250 So now we're going to create the new search function here. 10 00:00:49,280 --> 00:00:51,920 Integer search. 11 00:00:52,430 --> 00:00:57,620 And that's going to take the parameter integer array here and integer. 12 00:00:57,650 --> 00:00:59,510 Integer array. 13 00:00:59,510 --> 00:01:02,960 Size and integer X. 14 00:01:04,310 --> 00:01:06,230 So here we will. 15 00:01:06,350 --> 00:01:10,190 After that we will create a for loop to iterate through the array elements. 16 00:01:10,190 --> 00:01:17,510 So integer E equals zero while the E is less than array size. 17 00:01:19,390 --> 00:01:20,650 And E plus. 18 00:01:20,650 --> 00:01:21,190 Plus. 19 00:01:21,220 --> 00:01:21,940 Or plus. 20 00:01:21,940 --> 00:01:22,390 Plus E. 21 00:01:23,290 --> 00:01:23,530 Okay. 22 00:01:23,560 --> 00:01:24,250 Correct. 23 00:01:24,460 --> 00:01:29,530 And here, uh, the if our x here. 24 00:01:29,530 --> 00:01:35,210 If our x is found, return the index index of x here. 25 00:01:35,230 --> 00:01:47,110 So if our array dot e here is equals to x, then return E here. 26 00:01:47,140 --> 00:01:51,190 This means we found our, uh, searching element here. 27 00:01:51,190 --> 00:01:54,610 So if our x x is not found here. 28 00:01:54,610 --> 00:02:02,590 So if, uh, this loop, this condition is not executed, this means our X is not found here. 29 00:02:02,590 --> 00:02:07,060 So now we're going to create here this, uh, consider this as an else statement here. 30 00:02:07,060 --> 00:02:17,110 So if X is not found, then return, uh, if we then return or not here to be correct. 31 00:02:17,350 --> 00:02:21,860 If x is not found, then return the minus one. 32 00:02:22,010 --> 00:02:23,960 Return minus one here. 33 00:02:24,770 --> 00:02:31,400 As you can see here, this search function, it will find an index of target element. 34 00:02:31,580 --> 00:02:42,860 This is here X from an array, a a r r array containing a R size elements. 35 00:02:42,860 --> 00:02:45,650 So suppose we have the array of here. 36 00:02:45,680 --> 00:02:49,760 Let's actually create the 4255 and. 37 00:02:51,630 --> 00:02:53,700 Let's actually create our array here. 38 00:02:54,180 --> 00:02:57,270 So integer array. 39 00:03:00,290 --> 00:03:00,890 Here. 40 00:03:01,520 --> 00:03:05,580 So let's create our array here with five. 41 00:03:06,820 --> 00:03:07,900 Thanks for. 42 00:03:18,320 --> 00:03:19,970 Here is our array. 43 00:03:21,680 --> 00:03:26,210 And we will make this for example, our array size is going to be nine. 44 00:03:26,210 --> 00:03:34,970 So search, search, our array is going to be R, the array size is going to be nine. 45 00:03:35,000 --> 00:03:36,560 Oops, uh, nine. 46 00:03:36,560 --> 00:03:42,230 And what we want to find is, for example, 97. 47 00:03:43,580 --> 00:03:44,240 Here. 48 00:03:46,520 --> 00:03:47,930 If we run this program. 49 00:03:49,670 --> 00:03:54,920 Here we have no output, but we are code is compiled without an error. 50 00:03:54,920 --> 00:03:57,350 So we have the worst case. 51 00:03:57,380 --> 00:03:59,570 Let's actually start with the learning about the worst case. 52 00:03:59,570 --> 00:04:02,290 Actually, let's first print our here. 53 00:04:02,300 --> 00:04:11,060 So c out here, then print the array dot e here and make this. 54 00:04:14,180 --> 00:04:20,630 Found and re here and after that end line. 55 00:04:24,130 --> 00:04:25,630 And see out. 56 00:04:26,850 --> 00:04:28,830 Element not found. 57 00:04:30,500 --> 00:04:32,720 And new line and line. 58 00:04:33,770 --> 00:04:35,660 Let's run it again. 59 00:04:36,330 --> 00:04:39,040 And as you can see here, we found our array. 60 00:04:39,060 --> 00:04:43,650 So let's 22 and as you can see, we have no 22 in this array. 61 00:04:43,650 --> 00:04:49,890 And as you can see, we got an A finished with exit code because element is not found here. 62 00:04:51,400 --> 00:04:55,460 So let's get started with the worst case analysis. 63 00:04:55,480 --> 00:04:58,820 Average case analysis and best case analysis here. 64 00:04:58,840 --> 00:05:05,890 So worst case analysis is a calculation of the upper bound on the running runtime or of the running 65 00:05:05,920 --> 00:05:06,940 time of the algorithm. 66 00:05:06,940 --> 00:05:09,610 So in the search function. 67 00:05:09,940 --> 00:05:17,050 The upper bound can be an element that does not appear in the IRR. 68 00:05:17,440 --> 00:05:19,840 For instance, here 60. 69 00:05:19,990 --> 00:05:27,580 So it has to iterate through all elements of array IRR variable and still cannot find the element. 70 00:05:27,590 --> 00:05:30,310 So this is our worst. 71 00:05:32,080 --> 00:05:32,950 Case. 72 00:05:33,070 --> 00:05:35,710 We also have the average case here. 73 00:05:35,740 --> 00:05:36,790 Average. 74 00:05:37,770 --> 00:05:38,400 Case. 75 00:05:38,550 --> 00:05:45,090 So average case analysis is a calculation of all possible inputs on the running time of algorithm, 76 00:05:45,090 --> 00:05:49,890 so including an element that is not present in the arrays. 77 00:05:49,920 --> 00:05:53,340 We also have the best case. 78 00:05:54,000 --> 00:05:55,230 The best. 79 00:05:56,070 --> 00:06:02,100 Best case analysis is a calculation of the lower bound on the running time of the algorithm. 80 00:06:02,100 --> 00:06:07,770 So in the search function, the lower bound is the first element of the array, which is 45. 81 00:06:07,800 --> 00:06:15,060 So when we search for element 45, the function will only iterate through R only once. 82 00:06:15,060 --> 00:06:19,770 So the array size doesn't matter here. 83 00:06:27,460 --> 00:06:31,210 You can also do it like that and element not found. 84 00:06:32,800 --> 00:06:35,860 And continuing iterating. 85 00:06:36,100 --> 00:06:38,080 Element not found and iterating. 86 00:06:39,850 --> 00:06:40,210 Here. 87 00:06:41,910 --> 00:06:42,820 Run it again. 88 00:06:43,060 --> 00:06:48,730 And as you can see here, our element not found either here. 89 00:06:49,290 --> 00:06:51,270 That was the worst case scenario. 90 00:06:52,210 --> 00:07:00,730 The worst case scenario is whenever we found out, for example, 25, 21 or 14 here if we have 14. 91 00:07:02,180 --> 00:07:05,150 Of the race as it's going to be nine here. 92 00:07:05,420 --> 00:07:09,620 Our X here is going to be 14, for example. 93 00:07:11,290 --> 00:07:18,250 And as you can see here, after the iterating, one, two, three, four, five, six, seven, eight, 94 00:07:18,280 --> 00:07:22,090 nine, the 14 is found.