Now that we've spent a couple lectures talking about big O notation, it's time to start doing algorithm analysis on a data structure that I'll call a dynamic array. What are dynamic arrays? They're arrays that can grow and shrink as needed. This is a conceptual idea. There's no built-in dynamic array data type in C, so we'll have to do our own user-defined type for dynamic arrays. What operations might we want on the dynamic array? We want to find out how many valid values are in the array, we might want to print out the values in the array, and we might want to add a value to the array, remove a value from the array, or find a value in the array. Let's go look at the implementation details for that user-defined type and do algorithm analysis on each of those operations. Here's the code that goes along with the dynamic arrays reading. I'm going to cover some of the parts of this code. But to get a thorough understanding of all the details, you should make sure you go read that dynamic arrays reading as well. This constant expand multiply factor will tell us that anytime we need to grow the array, we'll actually double its size. We'll see that in action in a few minutes. But we know that when we create an array in C, we can't change its size after we've created the array. In dynamic arrays, we wanted to at least look like we are increasing the size of the array as needed. If it gets filled, we need to make it bigger, so we can add more elements to it. So we're going to use the expand multiply factor to actually grow the array when we need to. All these constants are just for manipulating the dynamic array as we execute our main function. I've got some constants that talk about function failing and function succeeding and the value not found. This is one of the pieces that's really critical to our understanding of dynamic arrays. The first one, this is the array itself. It will be values. As you can see, I've declared it as a pointer to an integer. We're going to treat it as a pointer here and in two other places in our code. But the rest of the time, we can just treat this as a normal array. So we don't have to worry about pointers too much. Just in a couple of places in our code. This next variable tells us how many valid values there are in the array. So let's say for example, that we start with an array that is of size four. We know if we haven't put anything into the array yet, that the number of valid values in that array is zero. So at any given time, our array typically has some valid values and some invalid values. All the valid values come first, and then all the invalid values come next. Using count will let us keep track of which of the values in our array are actually valid. Capacity tells us how big our array actually is. Because we're using pointers, we can't use sizeof to tell us how big our array is. So we're going to have to manually keep track of how big our array is, and capacity is the thing that we use to do that. Here are my function prototypes. We've seen this one numerous times before. These are just helper functions to help us run the operations against the dynamic array. Then we have the prototypes to actually do our operations on the dynamic array. We can add a value, we can find the value, we can remove a value, and we can print all the values in the array. I said that we'd also print out the count the number of valid values in the array. We'll see how we do that, but we don't actually need a function to do it. In my main function, here is one of the places that I treated the values array as a pointer, and I'm just allocating memory. Like we've seen before when we needed to create an array at runtime based on the size that we got at runtime, at least in Visual Studio. So we'll just continue with that approach here and we're going to say the capacity, which we know started at four, and we'll multiply it by size of int. So we're not creating a string here. We're not creating an array of characters. So we have to include the size of each element here and our multiplication, as we're allocating memory for the array. This is just asking the user what they want to do until they quit. So we can add a value, we can remove a value, we can find the value, we can print the count, and we can print the values. I said that printing the count doesn't require a separate function because, all we're going to do is print out the value of our count variable. This gives us an opportunity to do our first algorithm analysis. Accessing the value for a variable is a constant time operation. It's not a zero time operation because we have to go out to memory and get the value of the variable, but it's constant time. It takes the same amount of time every time, no matter how big the array is. So printing the count is a constant time operation which means that, it's order one. We'll zip past our helper functions and go to add value. Here's how add value works. First, when we're trying to add a new value to the array, we have to check to see if the array is already full. We can tell that by comparing count, how many valid values there are in the array. With capacity, how big is the array. So if count is four, we have four valid values. If capacity is also four that means the array is full. But we're trying to add one more value to it, so we need to grow the array. The first thing we do is multiply capacity by our expand multiply factor. So the first time we do this capacity is four and we're multiplying by two, so we're making our array eight instead of four. The next time, we would make it 16 instead of eight and so on. The next thing we do is set values to the result of calling the realloc function. This is the other place where we're treating values as a pointer rather than an array. This piece says here's how much memory I need. If we've just turned four into eight by multiplying by two, then this will be eight times the size of an int and we say where to start from. Now, there are two possibilities for how realloc will work. In the first case, if there's enough extra memory after where values as currently stored to give us the new amount of memory we need, then it just gives us that extra memory at the end of the current array. If in fact there isn't enough unused memory right after the values array, it will go find a different chunk of memory, that is the size that we need, and it will allocate that memory to us and, it will copy our existing values over into that new piece of memory. If values is null after we call realloc, it means the runtime system couldn't find a chunk of memory, that's the size we need, so we're failing and we return that here. If in fact though, we either have grown the array here or if this is false, we still had room in the array so we didn't have to grow it. We add the new value and increment count and say we succeeded. This might seem strange to you that we increment count after we've added the value rather than before, but remember this is zero-based indexing. So count actually tells us to different things. It tells us how many valid values we have in the array, which we've already discussed, and it also tells us the location at which we should add the next element to the array. That might feel confusing so think of it this way, the very first element we add to the array. When we get here, count is zero and values zero is definitely where we want to put that new value because zero is the location of the first element in our array, and then we increment count to one. So count is one and values zero is the value right where it's supposed to be, so everything is working fine here. What about the algorithmic complexity? If we don't need to grow the array, this is constant time, this is constant time and this is constant time. Into doing the check is constant time. So if we don't have to grow the array, this is a constant time operation, it's order one. What about if we do need to grow the array? We're actually faced with a problem here because this is order one and these are order one but we don't know the algorithmic complexity of realloc and unfortunately, the algorithmic complexity of realloc is not documented in the documentation either. So if in fact, even if it had to allocate new memory, if it copied all the values over as just one chunk no matter how big it is, then this would still be a constant time operation, but if it copies over one value at a time for example or a set number of bytes at a time, then this would be order n because the amount of time that it would take to get all those values copied over would be dependent on how many values we currently have. So we actually can't answer the question about the algorithmic complexity of add value if we need to grow the array, but we know it's constant time if we don't need to grow the array. Down here in find value, the way we look for a value is we do a for loop starting at the beginning of the array and going up to the last valid value. Notice this is not capacity this is count. We don't care about what values are invalid in the array, we only want to go up to the last valid value so we just do a for loop over those values and if we find that the value we're looking for, we return its index. But remember, algorithm analysis is about worst-case analysis, so what's the worst case? The worst case is, we either find the value we were looking for on the very last iteration of this loop or we don't find it at all and that's when we return value not found down here, but we know that we have to loop n-times in that worst-case where n is the number of valid values in the array. So that makes the find value operation order n. To remove a value from the array, the first thing we do is we call findValue so that we know where it is, so that we can remove it. We already know that find value is order n because we just did that algorithm analysis so we know removeValue is at best order n because of this call to the findValue function, but it could be worse. So we need to keep doing our analysis to find out if it is worth. It turns out that this is constant time and this is constant time. This line of code just takes the last valid value in the array, which is at location count minus one because of zero-based indexing and copies it into wherever the value that we're removing used to be in the array. So we can just copy the last one over onto the one that we're removing and then decrement count because now we have one fewer valid values in the array and now that we removed one and return function success. This is constant time, this is constant time, and this is constant time so all of these are constant time, but this is order n. So the removeValue operation is order n. The last function we need to look at is printing the values in the array, and you can tell here we're doing a for loop over all of the valid values in the array, printing each one as we go because this for loop iterate n times, the printValues operation is order n. To recap, in this lecture we got practice doing algorithm analysis on a variety of operations for our user-defined dynamic array datatype.
