1 00:00:07,720 --> 00:00:10,950 You've probably heard people talk about a fast or efficient algorithm 2 00:00:10,950 --> 00:00:13,090 for executing your particular task, 3 00:00:13,090 --> 00:00:16,110 but what exactly does it mean for an algorithm to be fast or efficient? 4 00:00:16,110 --> 00:00:18,580 Well, it's not talking about a measurement in real time, 5 00:00:18,580 --> 00:00:20,500 like seconds or minutes. 6 00:00:20,500 --> 00:00:22,220 This is because computer hardware 7 00:00:22,220 --> 00:00:24,260 and software vary drastically. 8 00:00:24,260 --> 00:00:26,020 My program might run slower than yours, 9 00:00:26,020 --> 00:00:28,000 because I'm running it on an older computer, 10 00:00:28,000 --> 00:00:30,110 or because I happen to be playing an online video game 11 00:00:30,110 --> 00:00:32,670 at the same time, which is hogging all my memory, 12 00:00:32,670 --> 00:00:35,400 or I might be running my program through different software 13 00:00:35,400 --> 00:00:37,550 which communicates with the machine differently at a low level. 14 00:00:37,550 --> 00:00:39,650 It's like comparing apples and oranges. 15 00:00:39,650 --> 00:00:41,940 Just because my slower computer takes longer 16 00:00:41,940 --> 00:00:43,410 than yours to give back an answer 17 00:00:43,410 --> 00:00:45,510 doesn't mean you have the more efficient algorithm. 18 00:00:45,510 --> 00:00:48,830 >> So, since we can't directly compare the runtimes of programs 19 00:00:48,830 --> 00:00:50,140 in seconds or minutes, 20 00:00:50,140 --> 00:00:52,310 how do we compare 2 different algorithms 21 00:00:52,310 --> 00:00:55,030 regardless of their hardware or software environment? 22 00:00:55,030 --> 00:00:58,000 To create a more uniform way of measuring algorithmic efficiency, 23 00:00:58,000 --> 00:01:00,360 computer scientists and mathematicians have devised 24 00:01:00,360 --> 00:01:03,830 concepts for measuring the asymptotic complexity of a program 25 00:01:03,830 --> 00:01:06,110 and a notation called 'Big Ohnotation' 26 00:01:06,110 --> 00:01:08,320 for describing this. 27 00:01:08,320 --> 00:01:10,820 The formal definition is that a function f(x) 28 00:01:10,820 --> 00:01:13,390 runs on the order of g(x) 29 00:01:13,390 --> 00:01:15,140 if there exists some (x) value, x₀ and 30 00:01:15,140 --> 00:01:17,630 some constant, C, for which 31 00:01:17,630 --> 00:01:19,340 f(x) is less than or equal to 32 00:01:19,340 --> 00:01:21,230 that constant times g(x) 33 00:01:21,230 --> 00:01:23,190 for all x greater than x₀. 34 00:01:23,190 --> 00:01:25,290 >> But don't be scared away by the formal definition. 35 00:01:25,290 --> 00:01:28,020 What does this actually mean in less theoretical terms? 36 00:01:28,020 --> 00:01:30,580 Well, it's basically a way of analyzing 37 00:01:30,580 --> 00:01:33,580 how fast a program's runtime grows asymptotically. 38 00:01:33,580 --> 00:01:37,170 That is, as the size of your inputs increases towards infinity, 39 00:01:37,170 --> 00:01:41,390 say, you're sorting an array of size 1000 compared to an array of size 10. 40 00:01:41,390 --> 00:01:44,950 How does the runtime of your program grow? 41 00:01:44,950 --> 00:01:47,390 For example, imagine counting the number of characters 42 00:01:47,390 --> 00:01:49,350 in a string the simplest way 43 00:01:49,350 --> 00:01:51,620 by walking through the whole string 44 00:01:51,620 --> 00:01:54,790 letter-by-letter and adding 1 to a counter for each character. 45 00:01:55,700 --> 00:01:58,420 This algorithm is said to run in linear time 46 00:01:58,420 --> 00:02:00,460 with respect to the number of characters, 47 00:02:00,460 --> 00:02:02,670 'n' in the string. 48 00:02:02,670 --> 00:02:04,910 In short, it runs in O(n). 49 00:02:05,570 --> 00:02:07,290 Why is this? 50 00:02:07,290 --> 00:02:09,539 Well, using this approach, the time required 51 00:02:09,539 --> 00:02:11,300 to traverse the entire string 52 00:02:11,300 --> 00:02:13,920 is proportional to the number of characters. 53 00:02:13,920 --> 00:02:16,480 Counting the number of characters in a 20-character string 54 00:02:16,480 --> 00:02:18,580 is going to take twice as long as it takes 55 00:02:18,580 --> 00:02:20,330 to count the characters in a 10-character string, 56 00:02:20,330 --> 00:02:23,000 because you have to look at all the characters 57 00:02:23,000 --> 00:02:25,740 and each character takes the same amount of time to look at. 58 00:02:25,740 --> 00:02:28,050 As you increase the number of characters, 59 00:02:28,050 --> 00:02:30,950 the runtime will increase linearly with the input length. 60 00:02:30,950 --> 00:02:33,500 >> Now, imagine if you decide that linear time, 61 00:02:33,500 --> 00:02:36,390 O(n), just wasn't fast enough for you? 62 00:02:36,390 --> 00:02:38,750 Maybe you're storing huge strings, 63 00:02:38,750 --> 00:02:40,450 and you can't afford the extra time it would take 64 00:02:40,450 --> 00:02:44,000 to traverse all of their characters counting one-by-one. 65 00:02:44,000 --> 00:02:46,650 So, you decide to try something different. 66 00:02:46,650 --> 00:02:49,270 What if you would happen to already store the number of characters 67 00:02:49,270 --> 00:02:52,690 in the string, say, in a variable called 'len,' 68 00:02:52,690 --> 00:02:54,210 early on in the program, 69 00:02:54,210 --> 00:02:57,800 before you even stored the very first character in your string? 70 00:02:57,800 --> 00:02:59,980 Then, all you'd have to do now to find out the string length, 71 00:02:59,980 --> 00:03:02,570 is check what the value of the variable is. 72 00:03:02,570 --> 00:03:05,530 You wouldn't have to look at the string itself at all, 73 00:03:05,530 --> 00:03:08,160 and accessing the value of a variable like len is considered 74 00:03:08,160 --> 00:03:11,100 an asymptotically constant time operation, 75 00:03:11,100 --> 00:03:13,070 or O(1). 76 00:03:13,070 --> 00:03:17,110 Why is this? Well, remember what asymptotic complexity means. 77 00:03:17,110 --> 00:03:19,100 How does the runtime change as the size 78 00:03:19,100 --> 00:03:21,400 of your inputs grows? 79 00:03:21,400 --> 00:03:24,630 >> Say you were trying to get the number of characters in a bigger string. 80 00:03:24,630 --> 00:03:26,960 Well, it wouldn't matter how big you make the string, 81 00:03:26,960 --> 00:03:28,690 even a million characters long, 82 00:03:28,690 --> 00:03:31,150 all you'd have to do to find the string's length with this approach, 83 00:03:31,150 --> 00:03:33,790 is to read out the value of the variable len, 84 00:03:33,790 --> 00:03:35,440 which you already made. 85 00:03:35,440 --> 00:03:38,200 The input length, that is, the length of the string you're trying to find, 86 00:03:38,200 --> 00:03:41,510 doesn't affect at all how fast your program runs. 87 00:03:41,510 --> 00:03:44,550 This part of your program would run equally fast on a one-character string 88 00:03:44,550 --> 00:03:46,170 and a thousand-character string, 89 00:03:46,170 --> 00:03:49,140 and that's why this program would be referred to as running in constant time 90 00:03:49,140 --> 00:03:51,520 with respect to the input size. 91 00:03:51,520 --> 00:03:53,920 >> Of course, there's a drawback. 92 00:03:53,920 --> 00:03:55,710 You spend extra memory space on your computer 93 00:03:55,710 --> 00:03:57,380 storing the variable 94 00:03:57,380 --> 00:03:59,270 and the extra time it takes you 95 00:03:59,270 --> 00:04:01,490 to do the actual storage of the variable, 96 00:04:01,490 --> 00:04:03,390 but the point still stands, 97 00:04:03,390 --> 00:04:05,060 finding out how long your string was 98 00:04:05,060 --> 00:04:07,600 doesn't depend on the length of the string at all. 99 00:04:07,600 --> 00:04:10,720 So, it runs in O(1) or constant time. 100 00:04:10,720 --> 00:04:13,070 This certainly doesn't have to mean 101 00:04:13,070 --> 00:04:15,610 that your code runs in 1 step, 102 00:04:15,610 --> 00:04:17,470 but no matter how many steps it is, 103 00:04:17,470 --> 00:04:20,019 if it doesn't change with the size of the inputs, 104 00:04:20,019 --> 00:04:23,420 it's still asymptotically constant which we represent as O(1). 105 00:04:23,420 --> 00:04:25,120 >> As you can probably guess, 106 00:04:25,120 --> 00:04:27,940 there are many different big O runtimes to measure algorithms with. 107 00:04:27,940 --> 00:04:32,980 O(n)² algorithms are asymptotically slower than O(n) algorithms. 108 00:04:32,980 --> 00:04:35,910 That is, as the number of elements (n) grows, 109 00:04:35,910 --> 00:04:39,280 eventually O(n)² algorithms will take more time 110 00:04:39,280 --> 00:04:41,000 than O(n) algorithms to run. 111 00:04:41,000 --> 00:04:43,960 This doesn't mean O(n) algorithms always run faster 112 00:04:43,960 --> 00:04:46,410 than O(n)² algorithms, even in the same environment, 113 00:04:46,410 --> 00:04:48,080 on the same hardware. 114 00:04:48,080 --> 00:04:50,180 Maybe for small input sizes, 115 00:04:50,180 --> 00:04:52,900 the O(n)² algorithm might actually work faster, 116 00:04:52,900 --> 00:04:55,450 but, eventually, as the input size increases 117 00:04:55,450 --> 00:04:58,760 towards infinity, the O(n)² algorithm's runtime 118 00:04:58,760 --> 00:05:02,000 will eventually eclipse the runtime of the O(n) algorithm. 119 00:05:02,000 --> 00:05:04,230 Just like any quadratic mathematical function 120 00:05:04,230 --> 00:05:06,510 will eventually overtake any linear function, 121 00:05:06,510 --> 00:05:09,200 no matter how much of a head start the linear function starts off with. 122 00:05:10,010 --> 00:05:12,000 If you're working with large amounts of data, 123 00:05:12,000 --> 00:05:15,510 algorithms that run in O(n)² time can really end up slowing down your program, 124 00:05:15,510 --> 00:05:17,770 but for small input sizes, 125 00:05:17,770 --> 00:05:19,420 you probably won't even notice. 126 00:05:19,420 --> 00:05:21,280 >> Another asymptotic complexity is, 127 00:05:21,280 --> 00:05:24,420 logarithmic time, O(log n). 128 00:05:24,420 --> 00:05:26,340 An example of an algorithm that runs this quickly 129 00:05:26,340 --> 00:05:29,060 is the classic binary search algorithm, 130 00:05:29,060 --> 00:05:31,850 for finding an element in an already-sorted list of elements. 131 00:05:31,850 --> 00:05:33,400 >> If you don't know what binary search does, 132 00:05:33,400 --> 00:05:35,170 I'll explain it for you really quickly. 133 00:05:35,170 --> 00:05:37,020 Let's say you're looking for the number 3 134 00:05:37,020 --> 00:05:40,200 in this array of integers. 135 00:05:40,200 --> 00:05:42,140 It looks at the middle element of the array 136 00:05:42,140 --> 00:05:46,830 and asks, "Is the element I want greater than, equal to, or less than this?" 137 00:05:46,830 --> 00:05:49,150 If it's equal, then great. You found the element, and you're done. 138 00:05:49,150 --> 00:05:51,300 If it's greater, then you know the element 139 00:05:51,300 --> 00:05:53,440 has to be in the right side of the array, 140 00:05:53,440 --> 00:05:55,200 and you can only look at that in the future, 141 00:05:55,200 --> 00:05:57,690 and if it's smaller, then you know it has to be in the left side. 142 00:05:57,690 --> 00:06:00,980 This process is then repeated with the smaller-size array 143 00:06:00,980 --> 00:06:02,870 until the correct element is found. 144 00:06:08,080 --> 00:06:11,670 >> This powerful algorithm cuts the array size in half with each operation. 145 00:06:11,670 --> 00:06:14,080 So, to find an element in a sorted array of size 8, 146 00:06:14,080 --> 00:06:16,170 at most (log₂8), 147 00:06:16,170 --> 00:06:18,450 or 3 of these operations, 148 00:06:18,450 --> 00:06:22,260 checking the middle element, then cutting the array in half will be required, 149 00:06:22,260 --> 00:06:25,670 whereas an array of size 16 takes (log₂16), 150 00:06:25,670 --> 00:06:27,480 or 4 operations. 151 00:06:27,480 --> 00:06:30,570 That's only 1 more operation for a doubled-size array. 152 00:06:30,570 --> 00:06:32,220 Doubling the size of the array 153 00:06:32,220 --> 00:06:35,160 increases the runtime by only 1 chunk of this code. 154 00:06:35,160 --> 00:06:37,770 Again, checking the middle element of the list, then splitting. 155 00:06:37,770 --> 00:06:40,440 So, it's said to operate in logarithmic time, 156 00:06:40,440 --> 00:06:42,440 O(log n). 157 00:06:42,440 --> 00:06:44,270 But wait, you say, 158 00:06:44,270 --> 00:06:47,510 doesn't this depend on where in the list the element you're looking for is? 159 00:06:47,510 --> 00:06:50,090 What if the first element you look at happens to be the right one? 160 00:06:50,090 --> 00:06:52,040 Then, it only takes 1 operation, 161 00:06:52,040 --> 00:06:54,310 no matter how big the list is. 162 00:06:54,310 --> 00:06:56,310 >> Well, that's why computer scientists have more terms 163 00:06:56,310 --> 00:06:58,770 for asymptotic complexity which reflect the best-case 164 00:06:58,770 --> 00:07:01,050 and worst-case performances of an algorithm. 165 00:07:01,050 --> 00:07:03,320 More properly, the upper and lower bounds 166 00:07:03,320 --> 00:07:05,090 on the runtime. 167 00:07:05,090 --> 00:07:07,660 In the best case for binary search, our element is 168 00:07:07,660 --> 00:07:09,330 right there in the middle, 169 00:07:09,330 --> 00:07:11,770 and you get it in constant time, 170 00:07:11,770 --> 00:07:14,240 no matter how big the rest of the array is. 171 00:07:15,360 --> 00:07:17,650 The symbol used for this is Ω. 172 00:07:17,650 --> 00:07:19,930 So, this algorithm is said to run in Ω(1). 173 00:07:19,930 --> 00:07:21,990 In the best case, it finds the element quickly, 174 00:07:21,990 --> 00:07:24,200 no matter how big the array is, 175 00:07:24,200 --> 00:07:26,050 but in the worst case, 176 00:07:26,050 --> 00:07:28,690 it has to perform (log n) split checks 177 00:07:28,690 --> 00:07:31,030 of the array to find the right element. 178 00:07:31,030 --> 00:07:34,270 Worst-case upper bounds are referred to with the big "O" that you already know. 179 00:07:34,270 --> 00:07:38,080 So, it's O(log n), but Ω(1). 180 00:07:38,080 --> 00:07:40,680 >> A linear search, by contrast, 181 00:07:40,680 --> 00:07:43,220 in which you walk through every element of the array 182 00:07:43,220 --> 00:07:45,170 to find the one you want, 183 00:07:45,170 --> 00:07:47,420 is at best Ω(1). 184 00:07:47,420 --> 00:07:49,430 Again, the first element you want. 185 00:07:49,430 --> 00:07:51,930 So, it doesn't matter how big the array is. 186 00:07:51,930 --> 00:07:54,840 In the worst case, it's the last element in the array. 187 00:07:54,840 --> 00:07:58,560 So, you have to walk through all n elements in the array to find it, 188 00:07:58,560 --> 00:08:02,170 like if you were looking for a 3. 189 00:08:04,320 --> 00:08:06,030 So, it runs in O(n) time 190 00:08:06,030 --> 00:08:09,330 because it's proportional to the number of elements in the array. 191 00:08:10,800 --> 00:08:12,830 >> One more symbol used is Θ. 192 00:08:12,830 --> 00:08:15,820 This can be used to describe algorithms where the best and worst cases 193 00:08:15,820 --> 00:08:17,440 are the same. 194 00:08:17,440 --> 00:08:20,390 This is the case in the string-length algorithms we talked about earlier. 195 00:08:20,390 --> 00:08:22,780 That is, if we store it in a variable before 196 00:08:22,780 --> 00:08:25,160 we store the string and access it later in constant time. 197 00:08:25,160 --> 00:08:27,920 No matter what number 198 00:08:27,920 --> 00:08:30,130 we're storing in that variable, we'll have to look at it. 199 00:08:33,110 --> 00:08:35,110 The best case is, we look at it 200 00:08:35,110 --> 00:08:37,120 and find the length of the string. 201 00:08:37,120 --> 00:08:39,799 So Ω(1) or best-case constant time. 202 00:08:39,799 --> 00:08:41,059 The worst case is, 203 00:08:41,059 --> 00:08:43,400 we look at it and find the length of the string. 204 00:08:43,400 --> 00:08:47,300 So, O(1) or constant time in worst case. 205 00:08:47,300 --> 00:08:49,180 So, since the best case and worst cases are the same, 206 00:08:49,180 --> 00:08:52,520 this can be said to run in Θ(1) time. 207 00:08:54,550 --> 00:08:57,010 >> In summary, we have good ways to reason about codes efficiency 208 00:08:57,010 --> 00:09:00,110 without knowing anything about the real-world time they take to run, 209 00:09:00,110 --> 00:09:02,270 which is affected by lots of outside factors, 210 00:09:02,270 --> 00:09:04,190 including differing hardware, software, 211 00:09:04,190 --> 00:09:06,040 or the specifics of your code. 212 00:09:06,040 --> 00:09:08,380 Also, it allows us to reason well about what will happen 213 00:09:08,380 --> 00:09:10,180 when the size of the inputs increases. 214 00:09:10,180 --> 00:09:12,490 >> If you're running in O(n)² algorithm, 215 00:09:12,490 --> 00:09:15,240 or worse, a O(2ⁿ) algorithm, 216 00:09:15,240 --> 00:09:17,170 one of the fastest growing types, 217 00:09:17,170 --> 00:09:19,140 you'll really start to notice the slowdown 218 00:09:19,140 --> 00:09:21,220 when you start working with larger amounts of data. 219 00:09:21,220 --> 00:09:23,590 >> That's asymptotic complexity. Thanks.