[MUSIC] When we analyze algorithms in computing, we often talk about their complexity and how they will scale. Complexity is a way of expressing the number of steps or operations in an algorithm. And the reason is an important is that it gives us an idea of how long it will take the algorithm to execute. Of course, we expect an algorithm to take longer if the input to the algorithm gets bigger. But how much longer? Complexity is therefore typically expressed as a function of the number of elements in the input data. Let's think about the two algorithms we've seen so far. Finding the maximum value in a collection, and determining whether a collection contains some value. In both cases, the operation we care about is the comparison between numbers, because that's what we're really doing here, making a bunch of comparisons. So let's measure the number of comparisons for these two algorithms, and understand it as a function of the input size. Here's the algorithm we saw a few lessons ago about finding a maximum value in the list. At first, the max is the first one in the list. We then look at each value in the list. If it's greater than the current max, then we use that as the max. After going through the entire list, the current max is the maximum value in the list. If the example we're finding the largest value. How many comparisons did we have to do? We called it initially, the first element was assumed to be the largest. And that no comparisons were done to determine that. Then, we looked at the next item and compared with the current max. This increases the number of comparisons by one, and changes the max to 81.2. Then, we looked at the next item and compare with the current max. This again increases the number of comparisons by one, but does not change the current max. We continue comparing items, increasing the number of comparisons at each point until we come to the end of the list. Here, we notice that there is a new max item, and keep comparing with the rest of the items. You can see that the number of comparisons is seven. We're done, so the number of comparisons remains seven. Which is one less then the length of the list. Now, what would happen if we doubled the number of elements, as shown here? Note that the top row is the original list of items, and we doubled it by adding a new row of items. Now, we have 16 values instead of eight, and we must compare against each one of them except for the first. Assume that we have processed the first row of numbers as shown on the previous slides, and are now comparing the max, which was 90.4, with the first element in the second row. This has added one to the number of comparisons. We continue as before, updating the number of comparisons. We are now done. This results in 15 comparisons, which is again one less than the length of the list. And if we had three times as many elements, it would again be one less than the length of the list. So with twice as many elements, we have roughly twice as many comparisons. And with three times as many elements, we have three times as many comparisons. This is called the linear growth. That is, the number of comparison operations is about the same as the number of elements. So for this reason, we say that the algorithm has linear complexity. Here's a graph showing linear growth. In this graph, the x-axis is the input size, or the number of elements. And the y-axis is the time that it takes to execute the algorithm, measured in terms of the number of operations. Note that the number of operations is roughly equal to the size of the input. So here, we have two inputs. Number of operations is two. Four inputs, number of operations is four. And that, as we increase the size of the input, the number of operations increases linearly. Now, let's talk about the complexity of the algorithm to determine whether a collection contains a value. It seems pretty similar to the find max algorithm because we have to look at each element in the list one by one. And we said that it had linear complexity because the number of operations grew linearly as the number of elements grew. But the problem is slightly different, right? Let's say we're looking for Wednesday at 2PM. We compare to the first element which is Friday at 3PM. That's one comparison. That's not the target, so we keep looking. Now we have two comparisons. In the example where it contains the target, searching for Wednesday at 2PM, we found it after considering only six of the eight elements. If we doubled the number of elements, it still would only take six comparisons to find that target. If it were still in the same place. We really don't care about how many elements come after that. So it seems like the number of operations wouldn't change if we doubled the number of elements. However, when we analyze the complexity of an algorithm, we usually care about the worst case. This gives us a better sense of what might happen when the size of the input grows. In this example, the worst case is when the list doesn't contain the target we're searching for. We can only determine that if we look at every element in the list. So let's say we're looking for Thursday at 12 PM. This results in eight comparisons. Since in the worst case we looked at every element in the list, if the number of elements increases, then we have to do more comparisons. In this case, we had eight numbers. And in the worst case, had to do eight comparisons. So what would happen if we doubled the number of elements? Now we have 16 meeting times, and we're still looking for Thursday at 12PM. The total number of comparisons is now 16. So if we double the number of elements to 16, then in the worst case, we have to do 16 comparisons. And the complexity is still linear, this is why the algorithm is known as linear search. When we analyze algorithms, we consider the number of steps or operations that need to be performed as a function of the input size. We looked at two algorithms, finding the maximum value and searching a collection for a value. Both were linear algorithms. In the case of finding the maximum value, we always had to look at every value in the input list. In the case of search, we could stop if the desired value was found in the list. However, in the worst case, when the value was not in the list, we had to look at every value in the input list. And when it comes to complexity, we are interested in the worst case performance as a function of the input size. The question is can we do better than linear complexity when searching for a value in an input collection? Well, I obviously wouldn't have brought it up if we couldn't. It turns out that this is the best we can do, if the elements are unordered. But if the collection was ordered, we can do better. That's what we'll look at next time.
