Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,203 --> 00:00:02,786 (techno music) 2 2 00:00:05,250 --> 00:00:07,180 Okay, so we've learned that arrays 3 3 00:00:07,180 --> 00:00:11,000 are very efficient when it comes to retrieving elements. 4 4 00:00:11,000 --> 00:00:12,370 They're also memory efficient 5 5 00:00:12,370 --> 00:00:15,250 because we don't have to store any extra information 6 6 00:00:15,250 --> 00:00:17,500 with each element in the array. 7 7 00:00:17,500 --> 00:00:18,560 You'll see later on 8 8 00:00:18,560 --> 00:00:21,100 that with many of the other data structures, 9 9 00:00:21,100 --> 00:00:23,000 we can't just store the value. 10 10 00:00:23,000 --> 00:00:25,360 We have to store extra information with the value, 11 11 00:00:25,360 --> 00:00:27,290 but that's not true for arrays. 12 12 00:00:27,290 --> 00:00:29,900 So arrays are efficient 13 13 00:00:29,900 --> 00:00:32,960 when you know the index of the value you wanna retrieve 14 14 00:00:32,960 --> 00:00:35,290 and they're also memory efficient. 15 15 00:00:35,290 --> 00:00:37,070 So let's quickly review here. 16 16 00:00:37,070 --> 00:00:40,370 To retrieve an element from an array when we have its index, 17 17 00:00:40,370 --> 00:00:44,810 we multiply the size of the element by its index, 18 18 00:00:44,810 --> 00:00:46,440 and remember every element in the array 19 19 00:00:46,440 --> 00:00:47,930 will have the same size, 20 20 00:00:47,930 --> 00:00:50,640 and multiplying the size of the element by its index 21 21 00:00:50,640 --> 00:00:55,110 gives us the offset from the beginning of the array. 22 22 00:00:55,110 --> 00:00:57,830 And then of course we need to start address of the array 23 23 00:00:57,830 --> 00:01:01,060 and we add the start address to the offset of the element 24 24 00:01:01,060 --> 00:01:04,660 and boom, we have the memory address of the element. 25 25 00:01:04,660 --> 00:01:08,800 So once again, to get intArray[0], 26 26 00:01:08,800 --> 00:01:11,160 if we're starting at address 12, 27 27 00:01:11,160 --> 00:01:13,190 assuming that's our array start address, 28 28 00:01:13,190 --> 00:01:16,940 that would be 12 plus zero times four which is 12. 29 29 00:01:16,940 --> 00:01:21,040 To get one would be 12 plus one times four to get 16, etc. 30 30 00:01:21,040 --> 00:01:24,830 So it doesn't matter how many elements we have in the array. 31 31 00:01:24,830 --> 00:01:26,950 If we have one element in the array, 32 32 00:01:26,950 --> 00:01:28,460 it's gonna take us three steps 33 33 00:01:28,460 --> 00:01:30,370 to retrieve the element, right? 34 34 00:01:30,370 --> 00:01:31,940 These three steps here. 35 35 00:01:31,940 --> 00:01:33,720 Any element in the array. 36 36 00:01:33,720 --> 00:01:35,910 If we have a thousand elements in the array 37 37 00:01:35,910 --> 00:01:39,500 and we have an index of an element, three steps. 38 38 00:01:39,500 --> 00:01:42,080 If we have a hundred thousand elements in the array 39 39 00:01:42,080 --> 00:01:45,030 and we wanna retrieve an element, three steps. 40 40 00:01:45,030 --> 00:01:46,700 A million elements, three steps. 41 41 00:01:46,700 --> 00:01:49,370 A billion elements, three steps. 42 42 00:01:49,370 --> 00:01:51,440 And so as you can see, 43 43 00:01:51,440 --> 00:01:55,580 unlike our adding sugar to your tea example, 44 44 00:01:55,580 --> 00:01:58,410 the number of steps does not change 45 45 00:01:58,410 --> 00:02:00,440 as the number of items changes. 46 46 00:02:00,440 --> 00:02:02,950 So if the number of elements is equal to n, 47 47 00:02:02,950 --> 00:02:05,610 the steps to retrieve never changes. 48 48 00:02:05,610 --> 00:02:07,500 And when we have this situation, 49 49 00:02:07,500 --> 00:02:11,610 we have what's known as constant time complexity 50 50 00:02:11,610 --> 00:02:15,270 and that's designated by O of one. 51 51 00:02:15,270 --> 00:02:18,850 And so our adding to sugar to tea algorithm 52 52 00:02:18,850 --> 00:02:21,860 had a linear time complexity which was O of n 53 53 00:02:21,860 --> 00:02:26,130 because n influenced how many steps were required 54 54 00:02:26,130 --> 00:02:27,960 in a liner fashion. 55 55 00:02:27,960 --> 00:02:32,300 But here when it comes to retrieving an element 56 56 00:02:32,300 --> 00:02:34,630 from an array when you have an array index, 57 57 00:02:34,630 --> 00:02:36,880 the number of items in the array 58 58 00:02:36,880 --> 00:02:39,450 has absolutely no effect on the number of steps. 59 59 00:02:39,450 --> 00:02:42,370 The number of steps is always going to be constant 60 60 00:02:42,370 --> 00:02:44,790 and so this has a constant time complexity 61 61 00:02:44,790 --> 00:02:46,240 which is O of one. 62 62 00:02:46,240 --> 00:02:50,080 It means that as the number of items increases, 63 63 00:02:50,080 --> 00:02:52,780 the algorithm doesn't degrade at all. 64 64 00:02:52,780 --> 00:02:54,640 So when it comes to retrieval, 65 65 00:02:54,640 --> 00:02:56,830 one of the advantages of arrays 66 66 00:02:56,830 --> 00:03:01,760 is that retrieving an element when you have its index 67 67 00:03:01,760 --> 00:03:06,240 can be done in O of one time which is the best you can get. 68 68 00:03:06,240 --> 00:03:08,950 And so that's one of the advantages of arrays. 69 69 00:03:08,950 --> 00:03:12,500 So let's take a look at some of the disadvantages of arrays 70 70 00:03:12,500 --> 00:03:14,193 so let's go back to the IDE. 71 71 00:03:18,110 --> 00:03:20,250 So we have our array here 72 72 00:03:20,250 --> 00:03:22,800 and let's say we read these numbers in a file 73 73 00:03:22,800 --> 00:03:25,730 or from a database or something so we don't see this. 74 74 00:03:25,730 --> 00:03:27,580 I mean, this could be anything. 75 75 00:03:27,580 --> 00:03:30,030 And then we have maybe an interface 76 76 00:03:30,030 --> 00:03:33,260 where we let a user type in search values 77 77 00:03:33,260 --> 00:03:35,390 and let's say the user typed something in 78 78 00:03:35,390 --> 00:03:37,130 and because of what they typed in, 79 79 00:03:37,130 --> 00:03:41,390 we want to retrieve the number seven from the array. 80 80 00:03:41,390 --> 00:03:43,760 Now remember you don't have this information. 81 81 00:03:43,760 --> 00:03:46,350 We're pretending we read values in from a file. 82 82 00:03:46,350 --> 00:03:50,840 We have no idea where integers were added into the array. 83 83 00:03:50,840 --> 00:03:53,037 So somebody comes along now and says, 84 84 00:03:53,037 --> 00:03:55,187 "Get me number seven from the array, 85 85 00:03:55,187 --> 00:03:57,420 "but I don't know what the index is." 86 86 00:03:57,420 --> 00:03:59,060 So all of a sudden, 87 87 00:03:59,060 --> 00:04:02,120 we can't just go right to the position in the array 88 88 00:04:02,120 --> 00:04:04,360 because we don't know the index for number seven 89 89 00:04:04,360 --> 00:04:05,700 so what do we have to do? 90 90 00:04:05,700 --> 00:04:07,680 Well, we're gonna have to do something like this. 91 91 00:04:07,680 --> 00:04:11,400 I'll change our code here and instead of printing out, 92 92 00:04:11,400 --> 00:04:16,400 we're gonna say if intArray[I] = 7 then we're done. 93 93 00:04:19,640 --> 00:04:22,630 So I'll say break, but what I'll do here is just say 94 94 00:04:22,630 --> 00:04:27,630 int index = minus 1 95 95 00:04:28,060 --> 00:04:31,370 and then when we find the seven we'll say index = i 96 96 00:04:31,370 --> 00:04:34,283 because that's the index for seven. 97 97 00:04:36,210 --> 00:04:39,050 And then after the loop we'll print the index. 98 98 00:04:39,050 --> 00:04:40,400 Let me make some room here. 99 99 00:04:49,120 --> 00:04:52,270 So we're expecting of course three to be returned 100 100 00:04:52,270 --> 00:04:53,170 so let's run 101 101 00:04:56,160 --> 00:04:59,340 and indeed the index that's returned is three. 102 102 00:04:59,340 --> 00:05:02,490 But we couldn't just jump to seven 103 103 00:05:02,490 --> 00:05:04,830 'cause we had no idea where seven was in the array. 104 104 00:05:04,830 --> 00:05:07,100 So when we've been talking about retrievals, 105 105 00:05:07,100 --> 00:05:08,670 we've been taking about retrievals 106 106 00:05:08,670 --> 00:05:11,040 when we know what the index is. 107 107 00:05:11,040 --> 00:05:13,300 In this case, we didn't know what the index is. 108 108 00:05:13,300 --> 00:05:14,560 Somebody came along. 109 109 00:05:14,560 --> 00:05:17,860 They didn't say give me the element at index three. 110 110 00:05:17,860 --> 00:05:20,880 Instead they said give me seven 111 111 00:05:20,880 --> 00:05:24,160 and that's all they said, give me the value seven, 112 112 00:05:24,160 --> 00:05:25,600 get that from the array 113 113 00:05:25,600 --> 00:05:27,580 and we're like well we don't know where it is 114 114 00:05:27,580 --> 00:05:29,360 so we had to search for it. 115 115 00:05:29,360 --> 00:05:32,140 And so remember for Big O notation, 116 116 00:05:32,140 --> 00:05:34,020 we always consider the worse case. 117 117 00:05:34,020 --> 00:05:36,920 So what would be the worse case for this? 118 118 00:05:36,920 --> 00:05:38,220 Well, the worse case would be 119 119 00:05:38,220 --> 00:05:41,660 that seven was in the last position in the array 120 120 00:05:41,660 --> 00:05:44,090 and so the worse case is that we had to search 121 121 00:05:44,090 --> 00:05:47,340 the entire array before we found seven. 122 122 00:05:47,340 --> 00:05:50,070 Now there are seven items in the array 123 123 00:05:50,070 --> 00:05:53,460 so n equals seven for this example 124 124 00:05:53,460 --> 00:05:56,960 and that means we would have had to have looped n times. 125 125 00:05:56,960 --> 00:05:58,910 And so in this situation, 126 126 00:05:58,910 --> 00:06:01,810 the number of elements does influence 127 127 00:06:01,810 --> 00:06:04,500 how many steps we're gonna have to perform. 128 128 00:06:04,500 --> 00:06:07,090 Because if we have 100 items in the array, 129 129 00:06:07,090 --> 00:06:08,350 then in the worse case, 130 130 00:06:08,350 --> 00:06:10,550 we're gonna have to loop 100 times. 131 131 00:06:10,550 --> 00:06:13,830 If we have a thousand items in the array, in the worse case, 132 132 00:06:13,830 --> 00:06:16,250 we're gonna have to loop a thousand times. 133 133 00:06:16,250 --> 00:06:18,610 If we have a million items in the array, 134 134 00:06:18,610 --> 00:06:20,320 worse case, a million times. 135 135 00:06:20,320 --> 00:06:24,420 So this looks like linear time complexity, right? 136 136 00:06:24,420 --> 00:06:27,700 Because when n is one, we have to loop once. 137 137 00:06:27,700 --> 00:06:30,220 When n is 10, we have to loop 10 times. 138 138 00:06:30,220 --> 00:06:33,240 When n is a thousand, we have to loop a thousand times. 139 139 00:06:33,240 --> 00:06:36,410 So it's progressing in a linear manner. 140 140 00:06:36,410 --> 00:06:39,780 And so retrieval when we know the index, 141 141 00:06:39,780 --> 00:06:42,320 we can do that in O of one time. 142 142 00:06:42,320 --> 00:06:45,450 But retrieval when we do not know the index, 143 143 00:06:45,450 --> 00:06:47,940 the O value for that is O of n 144 144 00:06:47,940 --> 00:06:50,680 because we have to find the item first 145 145 00:06:50,680 --> 00:06:51,770 and in the worse case, 146 146 00:06:51,770 --> 00:06:54,350 we'd have to loop over the entire array. 147 147 00:06:54,350 --> 00:06:57,540 So let's go back now to the slides 148 148 00:06:57,540 --> 00:06:59,770 so we can talk about the time complexity 149 149 00:06:59,770 --> 00:07:02,613 for some of the other array operations. 150 150 00:07:06,700 --> 00:07:09,610 Okay, we know that retrieving with an index, 151 151 00:07:09,610 --> 00:07:11,980 we went through this, is constant time. 152 152 00:07:11,980 --> 00:07:14,320 Now we just talked about retrieving an element 153 153 00:07:14,320 --> 00:07:15,860 when we don't know its index, 154 154 00:07:15,860 --> 00:07:17,980 that means we have to search the array. 155 155 00:07:17,980 --> 00:07:19,820 And in the worse case, 156 156 00:07:19,820 --> 00:07:22,330 we have to search the entire array 157 157 00:07:22,330 --> 00:07:24,950 so the time complexity is linear time. 158 158 00:07:24,950 --> 00:07:27,040 That's similar to the situation we had 159 159 00:07:27,040 --> 00:07:28,760 with putting sugars in the tea. 160 160 00:07:28,760 --> 00:07:32,540 The number of steps increases in a linear fashion 161 161 00:07:32,540 --> 00:07:34,560 as n increases. 162 162 00:07:34,560 --> 00:07:38,100 So let's think about adding an element to a full array. 163 163 00:07:38,100 --> 00:07:39,687 So with our intArray, 164 164 00:07:39,687 --> 00:07:42,000 it was already full so if we came along 165 165 00:07:42,000 --> 00:07:46,320 and for some reason we wanted to add an eighth integer, 166 166 00:07:46,320 --> 00:07:50,130 we can't add it into the array because the array is full. 167 167 00:07:50,130 --> 00:07:53,490 We've learned arrays are not a dynamic data structure. 168 168 00:07:53,490 --> 00:07:55,010 Their length is fixed. 169 169 00:07:55,010 --> 00:07:58,770 So the only way that we could add an integer, 170 170 00:07:58,770 --> 00:08:00,910 another integer into an array 171 171 00:08:00,910 --> 00:08:03,860 is if we created a brand new array 172 172 00:08:03,860 --> 00:08:08,310 that had a length large enough to take the existing integers 173 173 00:08:08,310 --> 00:08:09,640 and the new integer. 174 174 00:08:09,640 --> 00:08:12,520 So what we'd have to do is create a brand new array 175 175 00:08:12,520 --> 00:08:14,890 and then copy the integers over. 176 176 00:08:14,890 --> 00:08:18,130 And so this would also take linear time 177 177 00:08:18,130 --> 00:08:20,840 because creating the array 178 178 00:08:20,840 --> 00:08:23,610 doesn't depend on the number of elements 179 179 00:08:23,610 --> 00:08:26,340 and adding the new integer 180 180 00:08:26,340 --> 00:08:28,340 doesn't depend on the number of elements. 181 181 00:08:28,340 --> 00:08:31,040 We just have to know where in the array to add it, 182 182 00:08:31,040 --> 00:08:33,560 so we'd have the index for that, 183 183 00:08:33,560 --> 00:08:36,280 but we have to copy all the existing elements 184 184 00:08:36,280 --> 00:08:37,210 into the new array, 185 185 00:08:37,210 --> 00:08:40,410 which means we're gonna have to loop over the entire array. 186 186 00:08:40,410 --> 00:08:44,300 So once again, this is O of n, linear time. 187 187 00:08:44,300 --> 00:08:47,640 Now if we want to add an element to the end of an array 188 188 00:08:47,640 --> 00:08:49,190 that has space in it 189 189 00:08:49,190 --> 00:08:52,550 and assuming we know the index of where to add the element, 190 190 00:08:52,550 --> 00:08:54,330 well that's gonna be O to the one 191 191 00:08:54,330 --> 00:08:57,800 because that's similar to retrieving an element. 192 192 00:08:57,800 --> 00:08:59,490 When we have the index, 193 193 00:08:59,490 --> 00:09:01,500 we can figure out the memory address 194 194 00:09:01,500 --> 00:09:03,400 of where the new element is going to go 195 195 00:09:03,400 --> 00:09:05,560 just by using our simple calculation 196 196 00:09:05,560 --> 00:09:07,800 and so that's also constant time. 197 197 00:09:07,800 --> 00:09:11,660 And the same thing if we want to insert or update an element 198 198 00:09:11,660 --> 00:09:13,710 to this specific index. 199 199 00:09:13,710 --> 00:09:15,610 We can do that in constant time 200 200 00:09:15,610 --> 00:09:18,000 because if we have the index, 201 201 00:09:18,000 --> 00:09:20,120 we can jump right to the memory location. 202 202 00:09:20,120 --> 00:09:21,990 Now if we want to delete an element 203 203 00:09:21,990 --> 00:09:24,490 and we're gonna delete it by just setting it to null 204 204 00:09:24,490 --> 00:09:27,130 or in the case of integers zero or minus one 205 205 00:09:27,130 --> 00:09:28,280 or something like that, 206 206 00:09:28,280 --> 00:09:30,170 we can also do that in constant time 207 207 00:09:30,170 --> 00:09:32,890 because all we have to do, if we have the index, 208 208 00:09:32,890 --> 00:09:36,700 is jump right to the memory location. 209 209 00:09:36,700 --> 00:09:38,450 Now if we did not have the index, 210 210 00:09:38,450 --> 00:09:39,920 I don't have this on the chart, 211 211 00:09:39,920 --> 00:09:41,690 then it would take linear time 212 212 00:09:41,690 --> 00:09:44,860 because we'd have to search for the element first. 213 213 00:09:44,860 --> 00:09:46,777 So somebody came along and said, 214 214 00:09:46,777 --> 00:09:50,200 "Delete the number seven by setting it to minus one," 215 215 00:09:50,200 --> 00:09:52,560 we'd have to search through the array first 216 216 00:09:52,560 --> 00:09:54,110 to find the number seven. 217 217 00:09:54,110 --> 00:09:56,270 Now if we want to delete an element 218 218 00:09:56,270 --> 00:09:59,650 and we don't want to have nulls in our array 219 219 00:09:59,650 --> 00:10:01,990 or placeholders like minus one 220 220 00:10:01,990 --> 00:10:03,730 'cause that's basically dead space, 221 221 00:10:03,730 --> 00:10:06,660 so what we wanna do is when we delete an item 222 222 00:10:06,660 --> 00:10:07,580 in the middle of an array, 223 223 00:10:07,580 --> 00:10:10,400 we wanna shift all the other elements down. 224 224 00:10:10,400 --> 00:10:11,320 In the worse case, 225 225 00:10:11,320 --> 00:10:13,930 that will be O of n because in the worse case, 226 226 00:10:13,930 --> 00:10:15,700 we're gonna wanna delete the element 227 227 00:10:15,700 --> 00:10:17,460 right at the front of the array. 228 228 00:10:17,460 --> 00:10:19,680 And if we wanna shift all the other elements down, 229 229 00:10:19,680 --> 00:10:22,240 we're gonna have to loop over all the remaining elements 230 230 00:10:22,240 --> 00:10:23,860 and push them down. 231 231 00:10:23,860 --> 00:10:27,240 So that would be a linear time complexity. 232 232 00:10:27,240 --> 00:10:31,960 So essentially, if we have to loop over the array in any way 233 233 00:10:31,960 --> 00:10:34,130 in order to perform an operation, 234 234 00:10:34,130 --> 00:10:36,480 that's gonna have a linear time complexity. 235 235 00:10:36,480 --> 00:10:38,690 If we don't have to loop over the array 236 236 00:10:38,690 --> 00:10:40,880 because we have an index 237 237 00:10:40,880 --> 00:10:43,320 and so we can just calculate the memory address 238 238 00:10:43,320 --> 00:10:45,420 of the element we wanna work on, 239 239 00:10:45,420 --> 00:10:48,030 then that's going to have a constant time complexity. 240 240 00:10:48,030 --> 00:10:51,720 So an easy way for arrays to remember the time complexity 241 241 00:10:51,720 --> 00:10:54,350 is if the code requires a loop, 242 242 00:10:54,350 --> 00:10:55,940 it's gonna be linear time. 243 243 00:10:55,940 --> 00:10:57,920 If the code does not require a loop, 244 244 00:10:57,920 --> 00:10:59,420 then it's constant time. 245 245 00:10:59,420 --> 00:11:01,440 Now I've gone through this fairly quickly 246 246 00:11:01,440 --> 00:11:03,440 because we're talking about arrays 247 247 00:11:03,440 --> 00:11:05,530 and this isn't a beginner course 248 248 00:11:05,530 --> 00:11:07,740 so I assume that you know what an array is 249 249 00:11:07,740 --> 00:11:11,030 and you would have some idea of how to code for example 250 250 00:11:11,030 --> 00:11:13,970 retrieving an array element when you don't have the index 251 251 00:11:13,970 --> 00:11:17,320 or deleting an element when you don't have the index 252 252 00:11:17,320 --> 00:11:19,360 by setting it to null 253 253 00:11:19,360 --> 00:11:21,770 or adding an element to the end of an array 254 254 00:11:21,770 --> 00:11:24,950 that has space that you would know to write the code 255 255 00:11:24,950 --> 00:11:28,520 that keeps track of the last empty position, etc. 256 256 00:11:28,520 --> 00:11:30,220 So I'm not gonna code those. 257 257 00:11:30,220 --> 00:11:32,130 And that's all I'm gonna touch on for arrays 258 258 00:11:32,130 --> 00:11:34,550 because this really was meant to be a review 259 259 00:11:34,550 --> 00:11:37,380 and I wanna get into the sort algorithms. 260 260 00:11:37,380 --> 00:11:39,140 Now that we've looked at arrays 261 261 00:11:39,140 --> 00:11:41,600 and we have some idea of the time complexity 262 262 00:11:41,600 --> 00:11:44,100 for these different array operations, 263 263 00:11:44,100 --> 00:11:46,270 we can now get into sort algorithms 264 264 00:11:46,270 --> 00:11:48,590 and we have a way of comparing 265 265 00:11:48,590 --> 00:11:52,940 how well a sort algorithm performs compared to another one. 266 266 00:11:52,940 --> 00:11:54,683 So I'll see you in the next video. 23244