1 00:00:00,000 --> 00:00:04,879 [MUSIC] 2 00:00:04,879 --> 00:00:08,943 We have a vague understanding that Britney's approach is better in most cases 3 00:00:08,943 --> 00:00:12,218 but just like with linear search, it helps to visualize this. 4 00:00:12,218 --> 00:00:16,031 Much like we did with linear search when determining the efficiency of 5 00:00:16,031 --> 00:00:17,065 an algorithm, and 6 00:00:17,065 --> 00:00:20,764 remember we're still only looking at efficiency in terms of time. 7 00:00:20,764 --> 00:00:22,682 Time complexity as it's called. 8 00:00:22,682 --> 00:00:26,759 We always want to evaluate how the algorithm performs in the worse case 9 00:00:26,759 --> 00:00:27,460 scenario. 10 00:00:27,460 --> 00:00:31,921 Now you might be thinking that of that doesn't seem fair because given a series 11 00:00:31,921 --> 00:00:34,761 of data, if the target value we're searching for 12 00:00:34,761 --> 00:00:37,600 is somewhere near the front of the list then linear 13 00:00:37,600 --> 00:00:41,887 search may perform just as well if not slightly better than binary search. 14 00:00:41,887 --> 00:00:43,477 And that is totally true. 15 00:00:43,477 --> 00:00:47,788 Remember a crucial part of learning algorithms is understanding what works 16 00:00:47,788 --> 00:00:49,350 better in a given context. 17 00:00:49,350 --> 00:00:54,098 When measuring efficiency though, we always use the worse case scenarios as 18 00:00:54,098 --> 00:00:59,153 a benchmark, because remember, it can never perform worse than the worse case. 19 00:00:59,153 --> 00:01:04,233 Let's plot these values on the graph we started earlier, with the number of tries 20 00:01:04,233 --> 00:01:09,168 or the runtime of the algorithm on the y-axis, and the maximum number of values 21 00:01:09,168 --> 00:01:14,194 in the series, or n on the horizontal axis to represent the worst case scenario. 22 00:01:14,194 --> 00:01:15,662 We have two data points. 23 00:01:15,662 --> 00:01:19,455 When n equals 10, Britney took four tries using binary search. 24 00:01:19,455 --> 00:01:22,729 And when n equals 100, it took seven tries, but 25 00:01:22,729 --> 00:01:26,779 even side by side, these data points are sort of meaningless. 26 00:01:26,779 --> 00:01:27,682 Remember that, 27 00:01:27,682 --> 00:01:31,742 while there's quite a difference between the runtime of linear search and 28 00:01:31,742 --> 00:01:36,138 binary search at an n value of 100, for a computer, that shouldn't matter. 29 00:01:36,138 --> 00:01:40,940 What we should check out is how the algorithm performs at levels of n that 30 00:01:40,940 --> 00:01:43,511 might actually slow a computer down. 31 00:01:43,511 --> 00:01:48,487 As n grows larger and larger, how do these algorithms compare to one another? 32 00:01:48,487 --> 00:01:49,977 Let's add that to the graph. 33 00:01:49,977 --> 00:01:52,867 [SOUND] Okay, now a picture starts to emerge. 34 00:01:52,867 --> 00:01:54,392 As n gets really large, 35 00:01:54,392 --> 00:01:58,676 the performance of these two algorithms differs significantly. 36 00:01:58,676 --> 00:02:01,551 The difference is kind of staggering, actually. 37 00:02:01,551 --> 00:02:06,150 Even with the simple gain, we saw that binary search was better, but now, 38 00:02:06,150 --> 00:02:09,372 we have a much more complete idea of how much better. 39 00:02:09,372 --> 00:02:14,349 For example, when n is 1,000, the runtime of linear search measured 40 00:02:14,349 --> 00:02:18,149 by the number of operations or turns is also 1,000. 41 00:02:18,149 --> 00:02:21,785 For binary search, it takes just 10 operations. 42 00:02:21,785 --> 00:02:25,817 Now let's look at what happens when we increase n by factor of 10. 43 00:02:25,817 --> 00:02:26,985 At 10,000, 44 00:02:26,985 --> 00:02:32,611 linear search takes 10,000 operations while binary search takes 14 operations. 45 00:02:32,611 --> 00:02:37,245 An increase by a factor of 10 in binary search only needs four more 46 00:02:37,245 --> 00:02:39,409 operations to find the value. 47 00:02:39,409 --> 00:02:42,981 If we increase it again by a factor of ten once more, 48 00:02:42,981 --> 00:02:48,398 to an n value of 100,000, binary search takes only 17 operations. 49 00:02:48,398 --> 00:02:50,278 It is blazing fast. 50 00:02:50,278 --> 00:02:55,266 What we've done here is plotted on a graph how the algorithm performs 51 00:02:55,266 --> 00:02:58,456 as the input set it is working on increases. 52 00:02:58,456 --> 00:03:01,497 In other words, we've plotted the growth rate 53 00:03:01,497 --> 00:03:04,777 of the algorithm also known as the order of growth. 54 00:03:04,777 --> 00:03:09,132 Different algorithms grow at different rates, and by evaluating their growth 55 00:03:09,132 --> 00:03:12,846 rates, we're getting much better picture of their performance. 56 00:03:12,846 --> 00:03:17,809 Because we know how the algorithm will hold up as n grows larger. 57 00:03:17,809 --> 00:03:19,512 This is so important. 58 00:03:19,512 --> 00:03:23,972 In fact, it is the standard way of evaluating an algorithm, and 59 00:03:23,972 --> 00:03:26,458 brings us to a concept called big O. 60 00:03:26,458 --> 00:03:28,525 You might have heard this word thrown about. 61 00:03:28,525 --> 00:03:30,945 And if you found it confusing, don't worry. 62 00:03:30,945 --> 00:03:34,255 We've already built a definition in the past few videos. 63 00:03:34,255 --> 00:03:36,708 We just need to bring it all together. 64 00:03:36,708 --> 00:03:40,731 Let's start with a common statement you'll see in studies on algorithms. 65 00:03:40,731 --> 00:03:45,527 Big O is a theoretical definition of the complexity of an algorithm 66 00:03:45,527 --> 00:03:47,418 as a function of the size. 67 00:03:47,418 --> 00:03:48,838 Wow, what a mouthful. 68 00:03:48,838 --> 00:03:51,863 This sounds really intimidating but it's really not. 69 00:03:51,863 --> 00:03:52,950 Let's break it down. 70 00:03:52,950 --> 00:03:56,321 Big O is a notation used to describe complexity. 71 00:03:56,321 --> 00:04:01,210 And what I mean by notation is that it simplifies everything we've 72 00:04:01,210 --> 00:04:04,363 talked about down into a single variable. 73 00:04:04,363 --> 00:04:09,280 An example of complexity written in terms of big O looks like this. 74 00:04:09,280 --> 00:04:12,525 As you can see, it starts with an upper case letter O, 75 00:04:12,525 --> 00:04:14,270 that's why we call it big O. 76 00:04:14,270 --> 00:04:16,281 It's literally a big O. 77 00:04:16,281 --> 00:04:20,201 The O comes from order of magnitude of complexity. 78 00:04:20,201 --> 00:04:22,436 So that where we get the big O from. 79 00:04:22,436 --> 00:04:26,710 My complexity here refers to the exercise we have been carrying out in measuring 80 00:04:26,710 --> 00:04:27,489 efficiency. 81 00:04:27,489 --> 00:04:30,536 If takes Britney 4 tries when n is 10, 82 00:04:30,536 --> 00:04:34,761 how long does the algorithm take when n is 10 million? 83 00:04:34,761 --> 00:04:38,447 When we use big O for this, the variable used which we'll get to, 84 00:04:38,447 --> 00:04:42,805 distills that information down so that by reading the variable, you get a big 85 00:04:42,805 --> 00:04:47,517 picture view without having to run through data points and grasps just like we did. 86 00:04:47,517 --> 00:04:51,178 It's important to remember that complexity is relative. 87 00:04:51,178 --> 00:04:55,384 When we evaluate the complexity of the binary search algorithm, 88 00:04:55,384 --> 00:05:00,288 we're doing it relative to other search algorithms, not all algorithms. 89 00:05:00,288 --> 00:05:03,753 Big O is a useful notation for understanding both time and 90 00:05:03,753 --> 00:05:04,989 space complexity. 91 00:05:04,989 --> 00:05:09,847 But only when comparing amongst algorithms that solve the same problem. 92 00:05:09,847 --> 00:05:13,847 The last bit in the definition of big O is a function of the size, and 93 00:05:13,847 --> 00:05:18,217 all this means is that big O measures complexity as the input size grows. 94 00:05:18,217 --> 00:05:22,886 Because it's not important to understand how an algorithm performs in 95 00:05:22,886 --> 00:05:24,144 a single data set. 96 00:05:24,144 --> 00:05:26,007 But in all possible data sets. 97 00:05:26,007 --> 00:05:31,189 [SOUND] You will also see big O referred to as the upper bound of the algorithm. 98 00:05:31,189 --> 00:05:35,817 And what that means is that big O measures how the algorithm performs in 99 00:05:35,817 --> 00:05:37,550 the worst case scenario. 100 00:05:37,550 --> 00:05:40,635 So that's all they go is, nothing special. 101 00:05:40,635 --> 00:05:44,522 Is just a notation that condenses the data points and graphs. 102 00:05:44,522 --> 00:05:46,470 So we've built up down to one variable. 103 00:05:46,470 --> 00:05:49,181 Okay, so what do these variables look like? 104 00:05:49,181 --> 00:05:55,013 For John's strategy, linear search, we say that it has a time complexity of big O and 105 00:05:55,013 --> 00:05:59,156 then n, so that's again big O with an n inside parentheses. 106 00:05:59,156 --> 00:06:04,199 For Britney's strategy, binary search, we say that it has a time complexity of big 107 00:06:04,199 --> 00:06:09,040 O of log n, that's big O with something called a log and an n inside parentheses. 108 00:06:09,040 --> 00:06:10,857 Now don't worry if you don't understand that. 109 00:06:10,857 --> 00:06:14,251 We'll go into that in more detail later on in the course. 110 00:06:14,251 --> 00:06:16,427 Each of these has a special meaning but 111 00:06:16,427 --> 00:06:20,031 it helps to work through all of them to get a big picture view, so 112 00:06:20,031 --> 00:06:24,655 over the next few videos, let's examine what are called common complexities or 113 00:06:24,655 --> 00:06:28,607 common values of big O that you will run into and should internalize.