1 00:00:00,335 --> 00:00:01,916 At the beginning of this series, 2 00:00:01,916 --> 00:00:05,820 I mentioned that there were two ways of measuring the efficiency of an algorithm. 3 00:00:05,820 --> 00:00:08,149 The first was time complexity, or 4 00:00:08,149 --> 00:00:11,934 how the runtime of an algorithm grows as N grows larger. 5 00:00:11,934 --> 00:00:14,233 The second is space complexity. 6 00:00:14,233 --> 00:00:17,523 We took a pretty long route to build up this example, but 7 00:00:17,523 --> 00:00:20,821 now we're in a good place to discuss space complexity. 8 00:00:20,821 --> 00:00:25,322 Space complexity is a measure of how much working storage or 9 00:00:25,322 --> 00:00:29,745 extra storage is needed as a particular algorithm grows. 10 00:00:29,745 --> 00:00:32,557 We don't think about it much these days, but 11 00:00:32,557 --> 00:00:36,493 every single thing we do on a computer takes up space in memory. 12 00:00:36,493 --> 00:00:41,268 In the early days of computing, considering memory usage was of paramount 13 00:00:41,268 --> 00:00:45,303 importance because memory was limited and really expensive. 14 00:00:45,303 --> 00:00:48,519 These days we're spoiled, our devices are rich with memory. 15 00:00:48,519 --> 00:00:53,479 This is okay when we write everyday code because most of us aren't dealing 16 00:00:53,479 --> 00:00:55,810 with enormously large data sets. 17 00:00:55,810 --> 00:01:00,703 When we write algorithms however, we need to think about this because we want 18 00:01:00,703 --> 00:01:04,617 to design our algorithms to perform as efficiently as it can, 19 00:01:04,617 --> 00:01:07,953 as the size of the data set, N, grows really large. 20 00:01:07,953 --> 00:01:09,509 Like time complexity, 21 00:01:09,509 --> 00:01:14,811 space complexity is measured in the worst-case scenario using big O notation. 22 00:01:14,811 --> 00:01:19,158 Since you are familiar with the different kinds of complexities, 23 00:01:19,158 --> 00:01:21,494 let's dive right into an example. 24 00:01:21,494 --> 00:01:26,921 In our iterative implementation of binary search, the first one we wrote that uses 25 00:01:26,921 --> 00:01:31,978 a while loop, let's look at what happens to our memory usage as N gets large. 26 00:01:31,978 --> 00:01:34,486 Let's bring up that function. 27 00:01:34,486 --> 00:01:38,108 Let's say we start off with a list of ten elements. 28 00:01:38,108 --> 00:01:43,064 Now inspecting the codes we see that our solution relies heavily on these two 29 00:01:43,064 --> 00:01:44,851 variables first and last. 30 00:01:44,851 --> 00:01:48,357 First points to the start of the list and last, to the end. 31 00:01:48,357 --> 00:01:52,636 When we eliminate a set of values, we don't actually create a sublist. 32 00:01:52,636 --> 00:01:57,344 Instead we just redefine first and last as you see here, 33 00:01:57,344 --> 00:02:01,062 to point to a different section of the list. 34 00:02:01,062 --> 00:02:05,200 Since the algorithm only considers the values between first and 35 00:02:05,200 --> 00:02:09,183 last when determining the midpoint, by redefining first and 36 00:02:09,183 --> 00:02:14,710 last as the algorithm proceeds we can find the solution using just the original list. 37 00:02:14,710 --> 00:02:18,851 This means that for any value of n the space complexity of 38 00:02:18,851 --> 00:02:22,913 the interative version of binary search is constant. 39 00:02:22,913 --> 00:02:27,512 Or that the iterative version of binary search takes constant space. 40 00:02:27,512 --> 00:02:31,424 Remember that we would write this as big O of one. 41 00:02:31,424 --> 00:02:34,378 This might seem confusing, because as n grows, 42 00:02:34,378 --> 00:02:37,919 we need more storage to account for that larger list size. 43 00:02:37,919 --> 00:02:39,341 Now this is true, but 44 00:02:39,341 --> 00:02:43,777 that storage is not what space complexity cares about measuring. 45 00:02:43,777 --> 00:02:48,797 We care about what additional storage is needed as the algorithm runs and 46 00:02:48,797 --> 00:02:50,618 tries to find a solution. 47 00:02:50,618 --> 00:02:55,844 If we assume something simple, say that for a given size of a list, represented 48 00:02:55,844 --> 00:03:00,685 by a value N, it takes N amount of space to store it, whatever that means. 49 00:03:00,685 --> 00:03:05,880 Then for the iterative version of binary search, regardless of how large 50 00:03:05,880 --> 00:03:10,903 the list is, at the start, middle, and end of the algorithm process, 51 00:03:10,903 --> 00:03:15,037 the amount of storage required does not get larger than N. 52 00:03:15,037 --> 00:03:18,763 And this is why we consider it to run in constant space. 53 00:03:18,763 --> 00:03:23,039 Now, this is an entirely different story with the recursive version, however. 54 00:03:23,039 --> 00:03:27,330 In the recursive version of binary search we don't make use of variables to keep 55 00:03:27,330 --> 00:03:30,353 track of which portion of the list we're working with. 56 00:03:30,353 --> 00:03:35,328 Instead, we create new lists every time with a subset of values, or 57 00:03:35,328 --> 00:03:39,013 sublists, with every recursive function call. 58 00:03:39,013 --> 00:03:43,314 Let's assume we have a list of size n and in the worst case scenario, 59 00:03:43,314 --> 00:03:46,036 the target element is the last in the list. 60 00:03:46,036 --> 00:03:50,596 Calling the Recursive Implementation of binary search on this list and 61 00:03:50,596 --> 00:03:53,334 target would lead to a scenario like this. 62 00:03:53,334 --> 00:03:55,587 The function would call itself and 63 00:03:55,587 --> 00:03:59,946 create a new list that goes from the midpoint to the end of the list. 64 00:03:59,946 --> 00:04:05,090 Since we're discarding half the values, the size of the sublist is N by 2. 65 00:04:05,090 --> 00:04:07,533 This function will keep calling itself, 66 00:04:07,533 --> 00:04:11,300 creating a new sublist that's half the size of the current one, 67 00:04:11,300 --> 00:04:15,446 until it arrives at a single element list, and a stopping condition. 68 00:04:15,446 --> 00:04:19,829 This pattern that you see here, where the size of the sublist is reduced 69 00:04:19,829 --> 00:04:23,263 by a factor on each execution of the algorithmic logic, 70 00:04:23,263 --> 00:04:25,691 well we've seen that pattern before. 71 00:04:25,691 --> 00:04:26,956 Do you remember where? 72 00:04:26,956 --> 00:04:29,290 This is exactly how binary search works. 73 00:04:29,290 --> 00:04:33,702 [SOUND] It discards half the values every time until it finds a solution. 74 00:04:33,702 --> 00:04:36,049 Now we know that because of this pattern, 75 00:04:36,049 --> 00:04:38,943 the running time of binary search is logarithmic. 76 00:04:38,943 --> 00:04:39,543 In fact, 77 00:04:39,543 --> 00:04:44,422 this space complexity of the recursive version of binary search is the same. 78 00:04:44,422 --> 00:04:49,490 If we start out with the memory allocation of size N that matches the list, 79 00:04:49,490 --> 00:04:53,007 on each function call of recursive binary search, 80 00:04:53,007 --> 00:04:57,667 we need to allocate additional memory of size N/2, N/4, and so 81 00:04:57,667 --> 00:05:02,789 on until we have a sublist that is either empty or contains a single value. 82 00:05:02,789 --> 00:05:07,447 Because of this, we say that the recursive version of the binary 83 00:05:07,447 --> 00:05:12,035 search algorithm runs in logarithmic time with a big O of log N. 84 00:05:12,035 --> 00:05:14,252 Now, there's an important caveat here. 85 00:05:14,252 --> 00:05:16,992 This totally depends on the language. 86 00:05:16,992 --> 00:05:21,233 Remember how I said that a programming language like Swift can do some tricks to 87 00:05:21,233 --> 00:05:23,493 where recursion depth doesn't matter? 88 00:05:23,493 --> 00:05:25,897 The same concept applies here. 89 00:05:25,897 --> 00:05:30,457 If you care to read more about this concept, it's called tail optimization. 90 00:05:30,457 --> 00:05:35,218 It's called tail optimization because if you think of a function as 91 00:05:35,218 --> 00:05:40,226 having a head and a tail, if the recursive function call is the last line 92 00:05:40,226 --> 00:05:45,486 of code in the function, as it is in our case, we call this tail recursion, 93 00:05:45,486 --> 00:05:49,774 since it's the last part of the function that calls itself. 94 00:05:49,774 --> 00:05:53,889 Now the trick that Swift does to reduce the amount of space, and 95 00:05:53,889 --> 00:05:58,626 therefore computing overhead, to keep track of this recursive calls, 96 00:05:58,626 --> 00:06:02,762 is called tail call optimization, or tail call elimination. 97 00:06:02,762 --> 00:06:06,065 It's one of those things that you'll see thrown around a lot 98 00:06:06,065 --> 00:06:09,703 in algorithm discussions, but may not always be relevant to you. 99 00:06:09,703 --> 00:06:12,618 Now, what of any this is relevant to us? 100 00:06:12,618 --> 00:06:16,205 Well, Python does not implement tail call optimization. 101 00:06:16,205 --> 00:06:20,768 So the recursive version of binary search takes logarithmic space. 102 00:06:20,768 --> 00:06:24,068 If we had to choose between the two implementations, 103 00:06:24,068 --> 00:06:28,835 given that time complexity or run-time of both versions, the iterative and 104 00:06:28,835 --> 00:06:33,749 the recursive version are the same, we should definitely go with the iterative 105 00:06:33,749 --> 00:06:37,599 implementation in Python, since it runs in constant space. 106 00:06:37,599 --> 00:06:38,946 Okay, that was a lot. 107 00:06:38,946 --> 00:06:43,486 But all of this, with all of this we've now established two important ways 108 00:06:43,486 --> 00:06:47,308 to distinguish between algorithms that handle the same task, 109 00:06:47,308 --> 00:06:49,705 and determine which one we should use.