Analyzing the Time-Space Complexity

00:00 In this lesson, I’ll talk about the time-space complexity of binary search, and more generally.

00:07 So what do I mean, when I say time-space complexity? It kind of sounds like something from a science fiction movie, but really all it means is how long does it take your algorithm to run and how much space—in terms of computer memory—does it need to actually work.

00:24 When we talk about these kinds of things in computer science, we normally use Big O notation, and this is a really precise mathematical concept but, generally, that represents the worst case runtime of an algorithm as a function of the size of the input, which is often just called n.

00:42 So for example, you’d normally call linear search—which I showed you earlier—an O(n) algorithm because if your input list is n items long and the thing that you’re searching for is the last element in the list, it will take n comparison operations to find that thing. So for example, if I have a list here—1, 2, 3, 4, 5, 6, 7—these arrows are representing the search process.

01:05 So I check to look for 1 and I don’t find 7 there, so I keep going, and I keep going, and I don’t find 7, and I have to go all the way down to the last element to find 7, right?

01:18 So in the worst case in linear search, it will take you n operations to find the nth element in the list, right?

01:27 The space complexity of linear search, on the other hand, is called O(1), or constant, because you don’t need any space beyond the size of the input to implement the algorithm. Now technically, you might need a couple of variables to keep track of certain items, but as long as those are what’s called constant—as long as they don’t depend on the size of the input, so for example, if no matter how big the input is, I just need one pointer to tell me where I am in the list—then that’s totally fine and that’s called O(1).

01:56 Now, O(1) is the ideal, but an O(n) algorithm is still pretty darn good.

02:03 These are some common runtimes of algorithms on a color gradient to tell you how optimal they are. Now, algorithms can be divided into several different classes: so, a constant, log(n) runtime, O(n) runtime, n log(n), n squared, all the way up to n factorial. Now of course, you might have two constant time algorithms that run in dramatically different times. For example, if one of your algorithms always does only one operation and another algorithm always does exactly 10,000 operations, then they’re technically both constant time operations, but one is dramatically faster than the other. However, you know that if your input is gigantic, those two will always be faster than any of these other kinds of algorithms.

02:48 So, this is generally how you classify runtimes. Now, what is the time-space complexity of binary search and the other search algorithms that I showed you? Well, in binary search you have to again think about the worst case.

03:03 And the worst case scenario for binary search is when the item you’re looking for is at the beginning or the end of the list. And there’s some other places that will have similar time complexity, like right next to the middle element, but that’s not super important.

03:16 So, if you’re looking for something at the beginning of the list, you know that you cut away half of the list each time as you get down to just one element, the final element.

03:25 And I’ll save you some math by saying that, generally, you can put this on a chart and say, you know, your number of comparisons as each comparison happens, you eliminate half of the elements, and so you create this series here. And I’ll just cut to the chase and tell you that this normally takes log₂(n) comparisons to get down to one element.

03:46 And if you’d like to do the math, I would encourage you to check out different online resources that can do a little bit more complex of a job explaining that than I’m going to do right now.

03:57 But that’s why we call binary search a log(n) algorithm, or a log₂(n) algorithm. And in computer science more generally, whenever you see something that cuts away half of the search space in each time, you can feel comfortable saying it’s probably a log(n) algorithm. Now, how can you get even faster than that?

04:15 Because if you remember from the little chart I showed you, log(n) is almost as fast as it gets, but not quite. If you want to search in constant time, you need to make a tradeoff between time and space complexity, because binary search doesn’t require any extra space and if you want to go faster, you’re going to need to use some.

04:35 One way to speed up your search to constant time is by using a hash table, or as you might know it in Python, a dictionary, because hash tables are actually implemented by the Python dictionary. Now, the idea behind a hash table is that for each element in your list or whatever you’re looking to search, you have a hash function that maps that element to its index.

05:01 That is, when you call this hash function on your element, you get some kind of key that leads you to the index that it’s at. So in this example, the value "cat" would be mapped to its index of 2, "dog" mapped to its index of 0, and so on all the way down for all of the elements in the list. Now of course, to calculate all of these hash values at the beginning, you’re going to have to run through the entire list, so that’s an order of n operation.

05:27 But later, your look-ups are as fast as the hash function is, and that’s generally considered to be a constant time. Now of course, the tradeoff for this amazing speed is that hash tables use a lot more space than an algorithm like binary search or linear search, because they require you to store all of the elements in your list—the mapping from that element to its index. So, this is a data structure, which is at least order of n space. So, this was a quick run-through of time and space complexity in the search algorithms.

06:03 Next up is the conclusion.