Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Start a free Courses trial
to watch this video
With different algorithms performing different kinds of operations how do we figure out which algorithms are more efficient than others? In this video let's talk about Big O notation.
Glossary
- Order of growth - a measure of how much the time taken to execute operations increases as the input size increases
- Big O - a theoretical definition of the complexity of an algorithm as a function of the size
Resources
Runtime Data
Listed below are the data points used to plot the runtime graphs seen in the video
Linear Search
n | Worst case runtime |
---|---|
10 | 10 |
100 | 100 |
1000 | 1000 |
10000 | 10000 |
100000 | 100000 |
1000000 | 1000000 |
Binary Search
n | Worst case runtime |
---|---|
10 | 4 |
100 | 7 |
1000 | 10 |
10000 | 14 |
100000 | 17 |
1000000 | 20 |
[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
You need to sign up for Treehouse in order to download course files.
Sign up