WEBVTT Kind: captions Language: en 00:00:05.120 --> 00:00:10.160 You may have come across the term Big O, when looking at different algorithms. In this section, 00:00:10.160 --> 00:00:14.880 I'll explain what it is and why it's useful. I'll also be explaining what it's not. 00:00:14.880 --> 00:00:19.600 In particular, it doesn't guarantee that one algorithm will execute faster than another. 00:00:19.600 --> 00:00:22.720 It's basically a way to talk about the complexity of an algorithm, 00:00:22.720 --> 00:00:26.957 or the complexity of operations on a data structure. 00:00:28.400 --> 00:00:33.760 What I certainly won't be doing, is providing a rigorous, mathematical discussion of Big O. 00:00:33.760 --> 00:00:37.440 There's a good reason why I won't be doing that — the maths gets horrible. 00:00:37.440 --> 00:00:40.160 When we looked at the Wikipedia entry for Hash functions, 00:00:40.160 --> 00:00:44.720 back in the Dictionaries and sets section, there was some pretty scary maths in there. 00:00:44.720 --> 00:00:47.360 I encouraged you to skim through the article, because there were 00:00:47.360 --> 00:00:51.833 some interesting points that you could get from it, without worrying about the maths. 00:00:53.040 --> 00:00:56.800 Let's have a quick look at the Wikipedia article about Big O notation. 00:00:56.800 --> 00:01:00.000 I'll open that page in my browser. 00:01:03.120 --> 00:01:08.759 I don't suggest you read this, unless you're a mathematician, in which case it might make sense. 00:01:08.759 --> 00:01:12.000 For the rest of us, the only thing that will probably make sense, 00:01:12.000 --> 00:01:17.520 is the first sentence of the second paragraph: "In computer science, big O notation is used 00:01:17.520 --> 00:01:21.280 to classify algorithms according to how their run time or space requirements grow, 00:01:21.280 --> 00:01:25.640 as the input size grows." That's not too complicated. 00:01:25.640 --> 00:01:31.948 We use big O notation to indicate how much longer an algorithm will take, as we give it larger values to work on. 00:01:31.948 --> 00:01:36.329 Another way to think of that is, how many operations the algorithm has to perform. 00:01:36.400 --> 00:01:39.600 That sentence also talked about space requirements. 00:01:39.600 --> 00:01:44.560 We can use big O to talk about how much memory is needed, or how much disk space. 00:01:44.560 --> 00:01:48.880 That's the only sentence I suggest you read — unless you are a mathematician. 00:01:48.880 --> 00:01:54.000 The article opens by talking about "mathematical notation", and "limiting behaviour", and "tending 00:01:54.000 --> 00:01:59.200 towards infinity". If that wasn't bad enough, you don't have to scroll very far down, to see 00:01:59.200 --> 00:02:05.000 some really confusing formulae. Scroll until Formal Definition is at the top of your screen. 00:02:05.200 --> 00:02:09.579 That's horrible, and it only gets worse, the further you scroll down. 00:02:10.720 --> 00:02:14.000 The good news is, we don't have to understand all this. 00:02:14.000 --> 00:02:17.600 I'll summarise Big O notation with some slides. 00:02:18.364 --> 00:02:24.254 Big O notation is used to describe how the running time (or space requirements) of an algorithm grows, 00:02:24.254 --> 00:02:27.260 as you give it larger data sets to process. 00:02:27.260 --> 00:02:32.369 Programmers commonly use big O notation, rather than the other notations that are also available. 00:02:32.369 --> 00:02:38.728 Big O describes the upper bound. Some other notations are big omega notation, which uses the Greek letter Ω, 00:02:38.728 --> 00:02:42.582 and big theta notation, which uses the Greek letter Θ. 00:02:42.582 --> 00:02:47.444 They're used to describe a lower bound, and both a lower and upper bound, respectively. 00:02:47.444 --> 00:02:52.160 But this is starting to sound a bit mathematical again. So we'll stick with big O. 00:02:52.160 --> 00:02:57.090 In the tables that follow, I've listed the most common big O notations that you'll come across, 00:02:57.160 --> 00:03:00.090 with a brief description of what they mean. 00:03:02.000 --> 00:03:05.299 The notations appear in the order of how well they scale. 00:03:05.299 --> 00:03:08.640 As we get further into the slides, the algorithms will take increasingly 00:03:08.640 --> 00:03:13.760 larger amounts of time, as n increases. If we're applying them to memory usage, 00:03:13.760 --> 00:03:17.760 then the algorithms will use more and more memory, as n increases. 00:03:17.760 --> 00:03:24.373 The letter n refers to the number of items being processed. The size of the data, in other words. 00:03:26.560 --> 00:03:30.800 It's important to understand that big O doesn't tell you how fast an algorithm is. 00:03:30.800 --> 00:03:33.840 It's an indication of how the algorithm scales. 00:03:33.840 --> 00:03:38.499 By that, we mean how it performs when processing larger and larger data sets. 00:03:38.560 --> 00:03:44.585 Accessing an item in a list, using its index position, is O(1), or constant time. 00:03:44.585 --> 00:03:50.320 No matter how many items are in the list, we can go directly to any item by using its index position. 00:03:50.320 --> 00:03:54.960 Accessing the 900th item takes the same time, whether the list contains a thousand, 00:03:54.960 --> 00:03:58.446 a million, or several billion items. 00:04:00.079 --> 00:04:05.362 On the other hand, finding a value in an unsorted list is O(n) or linear time. 00:04:05.362 --> 00:04:12.160 If we have a list of 10 items, and we want to check if it contains "Python", then we might have to test 10 different values. 00:04:12.160 --> 00:04:17.280 If the list contains 1000 items, then we might have to check all one thousand entries. 00:04:17.280 --> 00:04:23.278 If the list is sorted, we can perform a binary search. That will execute in O(log n) 00:04:23.278 --> 00:04:27.840 We discussed the binary search in the Program flow control in Python section. 00:04:29.760 --> 00:04:33.764 Of course, the item we want might be the first item in the list. 00:04:33.764 --> 00:04:38.240 That means we'll find it straight away. Similarly, with a binary search, 00:04:38.240 --> 00:04:44.320 the item might be at the midpoint of the sorted list. If so, we'll also find it straight away. 00:04:44.320 --> 00:04:48.643 Which leads nicely onto the next slide: What does big O measure? 00:04:50.410 --> 00:04:53.920 Big O is used to measure the worst case of an algorithm. 00:04:53.920 --> 00:04:58.640 In the worst case, when the item we want is at the end of the list, then searching an unsorted list 00:04:58.640 --> 00:05:03.920 will involve checking every item in the list. With a list of 10 items, we'll find our item on 00:05:03.920 --> 00:05:10.320 the 10th try. With 1000 items, we'll compare 1000 values before we find the one we want. 00:05:10.320 --> 00:05:15.759 O(n) doesn't tell us that we'll need n operations. It tells us that, in the worst case, 00:05:15.759 --> 00:05:19.875 the time taken to find something will increase as the size of the list increases. 00:05:19.875 --> 00:05:25.349 Similarly, O(log n) implies that the algorithm's time increases as the log of n increases. 00:05:27.520 --> 00:05:30.800 Here are some of the most common big O notations that you'll come across, 00:05:30.800 --> 00:05:33.360 with a brief description of what they mean. 00:05:33.360 --> 00:05:38.320 The notations appear in the order of how well they scale. As we get further into the slides, 00:05:38.320 --> 00:05:43.443 the algorithms will take increasingly larger amounts of time, as N increases. 00:05:45.600 --> 00:05:48.480 O(1) means constant time. You can't get better than 00:05:48.480 --> 00:05:54.560 a constant time algorithm. It takes the same amount of time, no matter how large n becomes. 00:05:54.560 --> 00:05:58.640 Examples include retrieving a value from a list, using its index position; 00:05:58.640 --> 00:06:02.463 and getting a value from a dictionary, using its key. 00:06:04.400 --> 00:06:08.394 If you can find an algorithm that scales in the order of log n, O(log n) 00:06:08.394 --> 00:06:12.160 that's pretty good. Our binary search example was an O(log n) algorithm. 00:06:12.160 --> 00:06:16.480 We could get the correct value out of 10 numbers, with at most 4 guesses. 00:06:16.480 --> 00:06:21.488 When we increased the range of values to 1000, we only needed 10 guesses. 00:06:23.520 --> 00:06:27.760 The time taken by a linear algorithm increases directly as 'n' increases. 00:06:27.760 --> 00:06:33.520 For example, if we're processing 2 items, we might perform 2 operations. When we increase 00:06:33.520 --> 00:06:42.208 the number of items to 16, that will take 16 operations. 128 items takes 128 operations. 00:06:44.320 --> 00:06:49.840 n log n increases a bit faster than n, but not by a huge amount. We've seen that log n increases 00:06:49.840 --> 00:06:56.000 quite slowly, so n isn't being multiplied by large values. Using the previous example, processing 00:06:56.000 --> 00:07:03.840 2 items might take 2 operations (log 2 of 2 is 1). 16 items increases from 16 operations to 64 00:07:03.840 --> 00:07:13.920 (because log 2 of 16 is 4). With 128 items, the complexity increases to 128 * 7, which is 896. 00:07:13.920 --> 00:07:19.488 I know that looks like a huge increase over O(n), but wait till you see the next two entries! 00:07:21.360 --> 00:07:25.680 Things are now getting complex. That doesn't mean O(n) squared algorithms are bad, 00:07:25.680 --> 00:07:30.560 some tasks do require that much processing. But they slow down quite significantly, 00:07:30.560 --> 00:07:35.760 as you have larger data sets to process. Using our previous figures, we might have 4 00:07:35.760 --> 00:07:43.760 operations when processing 2 items; 256 operations with 16 items, and 16,384 operations when 00:07:43.760 --> 00:07:51.328 processing 128 items. As we increase the value of n, the computer has more and more work to do. 00:07:53.040 --> 00:07:58.320 We wrote a factorial function, in the Functions section, and saw that the factorial of 16 is over 00:07:58.320 --> 00:08:03.840 20 trillion. That's a lot of operations! Some tasks really are that complicated, 00:08:03.840 --> 00:08:09.680 and can take days to run, even on a supercomputer. [ Note: the travelling salesman problem can be 00:08:09.680 --> 00:08:16.135 reduced to O n squared * 2 to the power n, using some clever optimisations. That's still very slow, 00:08:16.135 --> 00:08:19.509 but an improvement over O(n! ) 00:08:20.752 --> 00:08:26.640 Those were some examples of Big O notations, describing how they increase as the data size increases. 00:08:26.640 --> 00:08:31.200 We also saw some examples of algorithms, for the various Big O notations. 00:08:31.200 --> 00:08:38.560 In the next video, we'll look at some graphs, to see how the complexities increase.