Efficiency of an Algorithm

[MUSIC] 0:00 We have a vague understanding that Britney's approach is better in most cases 0:04 but just like with linear search, it helps to visualize this. 0:08 Much like we did with linear search when determining the efficiency of 0:12 an algorithm, and 0:16 remember we're still only looking at efficiency in terms of time. 0:17 Time complexity as it's called. 0:20 We always want to evaluate how the algorithm performs in the worse case 0:22 scenario. 0:26 Now you might be thinking that of that doesn't seem fair because given a series 0:27 of data, if the target value we're searching for 0:31 is somewhere near the front of the list then linear 0:34 search may perform just as well if not slightly better than binary search. 0:37 And that is totally true. 0:41 Remember a crucial part of learning algorithms is understanding what works 0:43 better in a given context. 0:47 When measuring efficiency though, we always use the worse case scenarios as 0:49 a benchmark, because remember, it can never perform worse than the worse case. 0:54 Let's plot these values on the graph we started earlier, with the number of tries 0:59 or the runtime of the algorithm on the y-axis, and the maximum number of values 1:04 in the series, or n on the horizontal axis to represent the worst case scenario. 1:09 We have two data points. 1:14 When n equals 10, Britney took four tries using binary search. 1:15 And when n equals 100, it took seven tries, but 1:19 even side by side, these data points are sort of meaningless. 1:22 Remember that, 1:26 while there's quite a difference between the runtime of linear search and 1:27 binary search at an n value of 100, for a computer, that shouldn't matter. 1:31 What we should check out is how the algorithm performs at levels of n that 1:36 might actually slow a computer down. 1:40 As n grows larger and larger, how do these algorithms compare to one another? 1:43 Let's add that to the graph. 1:48 [SOUND] Okay, now a picture starts to emerge. 1:49 As n gets really large, 1:52 the performance of these two algorithms differs significantly. 1:54 The difference is kind of staggering, actually. 1:58 Even with the simple gain, we saw that binary search was better, but now, 2:01 we have a much more complete idea of how much better. 2:06 For example, when n is 1,000, the runtime of linear search measured 2:09 by the number of operations or turns is also 1,000. 2:14 For binary search, it takes just 10 operations. 2:18 Now let's look at what happens when we increase n by factor of 10. 2:21 At 10,000, 2:25 linear search takes 10,000 operations while binary search takes 14 operations. 2:26 An increase by a factor of 10 in binary search only needs four more 2:32 operations to find the value. 2:37 If we increase it again by a factor of ten once more, 2:39 to an n value of 100,000, binary search takes only 17 operations. 2:42 It is blazing fast. 2:48 What we've done here is plotted on a graph how the algorithm performs 2:50 as the input set it is working on increases. 2:55 In other words, we've plotted the growth rate 2:58 of the algorithm also known as the order of growth. 3:01 Different algorithms grow at different rates, and by evaluating their growth 3:04 rates, we're getting much better picture of their performance. 3:09 Because we know how the algorithm will hold up as n grows larger. 3:12 This is so important. 3:17 In fact, it is the standard way of evaluating an algorithm, and 3:19 brings us to a concept called big O. 3:23 You might have heard this word thrown about. 3:26 And if you found it confusing, don't worry. 3:28 We've already built a definition in the past few videos. 3:30 We just need to bring it all together. 3:34 Let's start with a common statement you'll see in studies on algorithms. 3:36 Big O is a theoretical definition of the complexity of an algorithm 3:40 as a function of the size. 3:45 Wow, what a mouthful. 3:47 This sounds really intimidating but it's really not. 3:48 Let's break it down. 3:51 Big O is a notation used to describe complexity. 3:52 And what I mean by notation is that it simplifies everything we've 3:56 talked about down into a single variable. 4:01 An example of complexity written in terms of big O looks like this. 4:04 As you can see, it starts with an upper case letter O, 4:09 that's why we call it big O. 4:12 It's literally a big O. 4:14 The O comes from order of magnitude of complexity. 4:16 So that where we get the big O from. 4:20 My complexity here refers to the exercise we have been carrying out in measuring 4:22 efficiency. 4:26 If takes Britney 4 tries when n is 10, 4:27 how long does the algorithm take when n is 10 million? 4:30 When we use big O for this, the variable used which we'll get to, 4:34 distills that information down so that by reading the variable, you get a big 4:38 picture view without having to run through data points and grasps just like we did. 4:42 It's important to remember that complexity is relative. 4:47 When we evaluate the complexity of the binary search algorithm, 4:51 we're doing it relative to other search algorithms, not all algorithms. 4:55 Big O is a useful notation for understanding both time and 5:00 space complexity. 5:03 But only when comparing amongst algorithms that solve the same problem. 5:04 The last bit in the definition of big O is a function of the size, and 5:09 all this means is that big O measures complexity as the input size grows. 5:13 Because it's not important to understand how an algorithm performs in 5:18 a single data set. 5:22 But in all possible data sets. 5:24 [SOUND] You will also see big O referred to as the upper bound of the algorithm. 5:26 And what that means is that big O measures how the algorithm performs in 5:31 the worst case scenario. 5:35 So that's all they go is, nothing special. 5:37 Is just a notation that condenses the data points and graphs. 5:40 So we've built up down to one variable. 5:44 Okay, so what do these variables look like? 5:46 For John's strategy, linear search, we say that it has a time complexity of big O and 5:49 then n, so that's again big O with an n inside parentheses. 5:55 For Britney's strategy, binary search, we say that it has a time complexity of big 5:59 O of log n, that's big O with something called a log and an n inside parentheses. 6:04 Now don't worry if you don't understand that. 6:09 We'll go into that in more detail later on in the course. 6:10 Each of these has a special meaning but 6:14 it helps to work through all of them to get a big picture view, so 6:16 over the next few videos, let's examine what are called common complexities or 6:20 common values of big O that you will run into and should internalize. 6:24