Hey, everyone. In this course, we're going to be learning about all the fundamental data structures and algorithms that you need to know, especially with a focus on coding interviews. This course is meant for beginners or anyone who just needs a refresher. We're going to be talking about the design, implementation, tradeoffs, and analysis of all the common data structures and algorithms. Being able to solve these problems efficiently, analyze them, discuss their tradeoffs, and then communicate the idea to others is what can make a difference in hundreds of thousands of dollars in compensation. I hope the problem-solving skills you learn in this course can serve you for your entire career. For more details on what we're going to cover, please scroll down. And when you're ready, let's get started. So the first digital structure that we're going to cover is arrays. But before we even get into that, let's first understand what even is a data structure. Well, as the name implies, it's a way of structuring data. But in our case, we're talking about computers. So we're going to be structuring this data inside of RAM. Let me show you what I mean. So suppose that this is our RAM in this case, and RAM is basically where all of our variables are going to be stored. So as we write code and as we use array data structures, let's say that this over here is our array, even though maybe we don't quite know what it is yet, we know that this is going to be stored in RAM. Let's say we have a one of three and a five in our array. So this is the information that we're trying to store. Now, how are we going to store it in RAM? Well, first of all, RAM is measured in bytes. It's common for many computers to have, let's say, eight gigabytes of RAM. What do we mean by gigabyte? Well, giga in this case means about 10 to the power of nine. So let's say that's about a billion. But the more important question is, what exactly is a byte? Well, a byte is nothing more than eight bits. So the next question is what exactly is a bit? A bit can be thought of as a position that can store a digit. But the restriction on the digit is that it can either be a zero or a one. You might already be familiar with this. Zeros and ones are the language of computers. And as you can already see, individual bits can form multiple bits, which can form bytes, which can form RAM and RAM can be used to store advanced data structures. But now let's get back to what arrays are. Now, in this case, we have an array of integers, as you can tell.  So in this case, we have an integer one. How can we store this integer one in our RAM? Well, we have to store it in terms of bytes. Now, it's pretty common for integers to be represented not by a single byte, but actually as four bytes. So what that would mean is instead of using eight bits, we would actually have, let's say 32 bits. I'm not going to draw all of them out, but you can assume that we have in total over here, we have 32 bits. So how are we going to represent this one? Well, we're going to talk about this a little more in depth later in the course. But for now, I'll just tell you that it's going to be 31 zeros. And then all the way at the end, we're going to have a single one. So what's important here is that we have a way to take this one, you know, represent it in terms of bytes, and then we're allowed to put that into RAM. Now, while RAM can be thought of as a contiguous block of data, it also has two components to it. Of course, we're going to be storing values in our RAM, but every value is going to be stored at a distinct location, which we call an address. Now, I've put a dollar sign in front of every address just to kind of distinguish that between the values that we're going to be storing. But what you can see here is that the first address is zero. Now, as we store an array in RAM, we don't always get to choose what location it's going to be at. But one thing about arrays is that they're always going to be contiguous. What that means is here, we're going to be storing the one here, we're going to be storing the three and here, we're going to be storing the five. So nothing is going to be in between the three that we have stored over here, and the five that we have stored over here, nothing is going to be in between that. But if that's the case, why am I incrementing the address by four every time? Shouldn't this be stored at zero? This should be stored at address one. This should be stored at address two. Well, remember, each value takes four bytes to store. So this doesn't represent one byte, it represents four bytes. So we're storing 32 bit integers. That means they take four bytes to store. Now this might seem very straightforward. And it is for the most part. And that's because arrays are considered the most simple data structure. We just store them pretty much the same way that we're representing them here. In memory, they look the exact same as they do the way we use them. A contiguous set of values. Now in this case, we're storing integers, but we could be storing other values as well. Let me show you what it would look like if instead we were storing characters like ABC. Characters are stored pretty much exactly the same contiguously as we would expect. But you notice the address is a bit different. In this case, we're incrementing by one as we add a new character. That's because each character actually only takes one byte to store in memory, not four bytes. At least that's the typical case if we're storing ASCII characters, which isn't super important to know what I'm getting at, though, is we can store values contiguously, regardless of how big or small they are, as long as we increment our address by the size of the value. So this was definitely a lot of theory to understand. But don't worry, this course is mostly going to focus on practical knowledge. But at least we learned a bit about what memory is and how arrays can be stored in memory. Now it's time to understand how arrays can be used and what exactly are its properties and tradeoffs up next. Now let's discuss the properties of arrays. But first to review, we know that an array is a contiguous block of data. We know it stored the same way in RAM. It's stored as a contiguous block of data. Now with any data structure, the two most common operations are reading to the data or writing to the data. We're going to first handle the simple case, which is reading the data. Let's suppose we want to read the first element of our array. Well, as a programmer, we have an array. Let's say we allocated it by calling it my array. So this is a variable that we have to read the first element. The intuitive thing is to go in memory at the first address and then read the value. Now that's exactly what's happening under the hood. But we as programmers don't need to know the exact address of every single value. As we use the array, we use indexes to access values. The first value is always at index zero, not at index one, that can be confusing if you're a beginner, but it's always starting at zero. The next one is at one. And the next one is at two, et cetera, et cetera. So when we read the first value, which is at index zero, it's automatically going to go to this location in our memory and read the value that's stored in memory. Since we can automatically map any index in our array to a location in memory, that means we can instantly read any value as long as we have the index for it to represent that that's an efficient operation. We call it big O of one. We're going to talk more about big O notation later in the course. But for now, what this means is that in the worst case to read a value, assuming we have the index. So suppose we want to read the value at index two, it's an instant operation. It happens in constant time. No matter how big our array gets, if we want to read any value in the array, we can read it instantly. That's what big O of one means. At least that's the oversimplified explanation so far. The fact that we can go to any arbitrary address in our RAM and then read the value at that address is a property of RAM. It's actually in the name itself. Random access memory is what RAM stands for. It basically means we can randomly access any portion of the memory in constant time. Suppose if we wanted to access this value, we don't have to start from the beginning of our RAM and then keep looking for it. We can automatically access it. And that's pretty important, as you can tell, because if we have a lot of RAM, we don't want to have to go through the entire RAM every single time. If we want to access the third value in the array, we don't want to have to go through the first and second values because it's not necessary for us. Now, after we read our first value, next we want to read the second value and the third value and keep doing that until we get to the end of the array. That's pretty easy. We know that the first index we start at is, let's say, zero, I'm going to call it I in code, we would typically say my array at index I to read the value. And then of course, we would increment the I to be one. And then we would increment it to be two. And we would keep doing that until it equaled the length of the array. And then we would stop. So essentially, we would loop through the entire input array. In most languages, you can do so with a for loop or a while loop. Now, while this might seem really simple, the ideas that we're talking about now are going to be the building blocks for very advanced algorithms, we talk about later in the course. So we talked about reading from an array. Now it's time to talk about writing to an array, which is going to bring us to an important properties of arrays, which is that they're of fixed size. In this case, we declared an array of three values. It's fixed size. Suppose we want to add a fourth value to it, let's say a seven. Well, taking a look at our model of memory. So the simple thing to do would just be add a seven in memory. But we have to make sure it's contiguous. So we would do so only at address 12. So then we have an array of size four, and it's still contiguous. This seems like it might work. But the way Ram works, we don't always get to decide exactly where we allocate our Ram. We don't always get to decide exactly where we store our values. And we don't know for sure that this spot in Ram is even available for us. It could be that we already have maybe another array stored over here, or maybe the operating system is using this part of our memory for some other purpose. So we're not necessarily allowed to put the seven over here. Okay, then you might think, Well, let's just let the operating system decide. Just just put a seven anywhere in memory. But if we do that, we don't follow the property of arrays. It's no longer contiguous. Now we have two arrays. That's not what we wanted. We wanted a single array because if we do it like this, and then let's say I'm looping through this array, I'm at index two. Now I increment and I'm at index three. What we're going to try to do by accessing this is we're going to go to this spot. But we don't know that the seven is stored over here. It might be stored somewhere else. So this is going to break. Basically, we've come across the biggest limitation of arrays, at least for static arrays, which is what we've talked about so far. static arrays basically mean that they're fixed size arrays. So before we continue to discuss the limitations of static arrays, I do want to mention if you're used to a programming language like Python or JavaScript, you might have never come across this limitation, because those languages don't really offer static arrays. You never have to worry about running out of space when you're using an array. And that's because those languages usually offer dynamic arrays as the default, which we're going to discuss later on. So suppose we allocated an array of size three, initially it's empty. But there has to be something stored here. And usually by default languages will initialize it to be all zero, or sometimes they won't initialize it at all. And sometimes there can just be some random values here, like just some random arbitrary values that we didn't even put there. So initially, we have some space, let's say we start adding values to it, we add a five, that puts a five in memory, we add a six, that puts a six in memory, we add a seven, that puts seven in memory. Now we're allowed to remove values. But when we say remove, we can't actually delete this in memory. We can't deallocate that with a static array. When we say remove a value, we're basically saying we're going to overwrite it by putting, let's say zero in that case. And we would say that this value is no longer relevant. We have a zero here. We only care about these two. This is still in memory, but we don't care about it. And we can, you know, remove all the values in a similar way. But what we can't do is add a new value. By the way, as we add a new value to the end of the array at the next empty spot that we're keeping track of, it's also going to be an instant operation. Because we know this is index zero, this is index one, we want to write to this position. Therefore, we know instantly that we're writing to this position in RAM. So writing to any position is also a big O of one operation. It's constant time, we can think of it as an instant operation. Similarly, removing a value is also as efficient as big O of one. It's a constant time operation because what we're really doing is just going to that position in memory and xing it out. We could be replacing it with a zero or a negative one or something like that. We're not actually deleting it, but we're overwriting it. So these are the efficient operations with a static array. So we have a couple values in our array. And remember, these are ordered values. The five comes before the six. We know that because of the way the indexes work. So let's say we wanted to arbitrarily insert a value into the middle of the array at any position in the middle of the array. By that, I mean any position in between these values at the end of these values or at the beginning, we know inserting at the end is always efficient because we're inserting into an empty spot. If at least there's one available, we're assuming that there is space available. That's efficient. That's O of one. But inserting at any arbitrary position, like the middle or at the beginning is not going to be efficient because let's say I want to insert the value for at this position.  What we actually want is to have four, five, six. We could put the four over here because that's efficient. It's all of one. And there is space there. But that doesn't achieve four, five, six. We're we have the elements out of order with arrays, including static arrays. The order of the values does matter. So for us to insert the four, over here, we first have to shift the five to the next position. But if we shift it over here, we're going to get rid of the six. That's not what we want to do. So before we shift the five, we have to shift the six, and then we shift the five. In other words, we're going to take the six. It's at index one, but we're going to set it to be index one plus one, meaning it's going to be at index two. So the six is going to go there. The same thing with the five, it's going to go at index zero plus one, which we know is one. So it's going to go here. Only after we've performed this shifting, are we allowed to put the four over here? There's space for it now. And we preserved the order of the values. The downside of this is we couldn't do it in a single operation. We had to move every value in the array. In this case, we only had two values in the array. But imagine if we had a really long array and it was all filled with some values, and we wanted to insert a value at the beginning, then we'd have to take all of these shift them, and then we could insert the new value. This is not very efficient. That's what I'm getting at. We call this a big O of N operation and in this case refers to a variable. And in this problem, N refers to the number of elements in the array. We can call that the length of the array length, meaning the actual values we have not the size of the array, but the number of values. And I've been using big O. But what it actually means is the worst case because this what we just did right now was the worst case. What we had to do is we had to shift every value in the array, which means N values over to the right by one. And then we were allowed to insert the new value. But if we were inserting in the middle between five and six, let's say what we actually wanted to do was have a five and then a four and then a six, then we wouldn't have had to shift the five at all. We would only have had to shift the six, the five would have stayed over here on the left, and we would have inserted the four over here. So in that case, we would have only needed to shift one value, not every value in the array. But we don't want to go through every possible scenario. So we generalize it. We say in the worst case, if you're inserting a value in the middle of the array at any arbitrary position in the worst case, we might have to shift every value. We might have to shift N values. So in the worst case, the time complexity is going to be big O of N. And the exact same thing is true if we're removing a value at any arbitrary index. When I say removing, I'm not just saying, you know, put replacing it with a zero or something. I'm saying I don't even I want to pretend like this doesn't exist anymore. I want the first value to be six. In that case, we would do something similar, but we would take the six and then shift it to the left by one. So we would say one minus one is going to be zero. So we're going to put it at the zeroth index. Seven is at index two, we're going to take two minus one, which is one, and we're going to move this to that index. In the end, we're left with a six, seven. Technically, the seven from over here would still be there, or we could have replaced it with a zero, or we could, you know, do something to pretend like it doesn't exist. But the memory that we actually allocated here definitely does exist. And it would be, you know, reflected in RAM. So to summarize the operations for a static array reading or overriding the ith element of an array, ith basically means any arbitrary element, you could pick any index and read or write from it. You can do that in big O of one time, you can do that in constant time to insert a value at the end of the array, or to remove the value at the end of the array is also a big O of one time operation. That's assuming that we have an empty space left at the end, or we at least have one element at the end for us to remove. Now, inserting into the middle of an array in the worst case is going to be big O of N. For an empty array to insert in the middle, it would be very efficient. It would be one big O of one. But we know we're talking about the worst case. That's what big O refers to. To insert in the middle would be big O of N. We might have to shift every value in the array. The same thing for removing in the middle, we might have to shift every value in the array. Next, let's move on to dynamic arrays, which are much more common and much more useful than static arrays. You've probably already used a dynamic array, you just might not have known it. In Python and JavaScript, dynamic arrays are the default. In Java, you can use an array list or in C plus plus, you can use a vector. So let's remember that the problem we're trying to solve here is the fixed size problem. Our static array is a fixed size. But what if we have an array that is dynamic in this case? Now, when we were creating static arrays, we usually have to specify the size. So when we were using static arrays before of size three, we specified that it was size three when we created that array. But in this case, let's say this is a dynamic array, and we created a dynamic array, but we didn't initialize any of the values. And with dynamic arrays, you don't necessarily have to specify the size. If you don't specify the size, usually it'll initialize it to some default size. For example, in Java, I think usually the default size of an array list is 10. But that number could be arbitrary. And it's not necessarily important. Let's say we initialized a default empty dynamic array, let's just say it got initialized to size three in this case. While the size is three, the length of the array is actually zero in this case, we have nothing added to it yet. So we say the length is zero. Now, as we add elements to the end of the array, we call that pushing to the array. So we're pushing to the end of the array, we pushed a zero to the array. Now we're going to push another element. And what that means is insert it at the next empty spot. So let's push a four in this spot. Now with the internal implementation of this dynamic array, it will maintain a pointer or basically a variable telling us what index is the last element of this array. So we know that the first element is at index zero, the next element is at index one. And we know this is the last element so far. So we have a pointer telling us that this is where the last element is, we can also use this pointer to get the length of the array. So right now, this pointer is at index one. That means the length of the array must be two, because remember, we're starting at zero. So we talked about pushing, but we can also pop values popping in this case also refers to the end. So that's why this end pointer is important for us, we're going to pop the last value, just like how pushing a value to the end is an O of one time operation, popping a value from the end is also a big O of one time operation because we know exactly where that value is because we have that pointer to the last element, we pop it. And we also want to now take this pointer and then shift it to the left by one. So now we're maintaining that this is the new end of our array. We could also pop this value as well, which would make our array be basically of length zero again. But that's the main idea. Now for the problem we're trying to solve Let's push another element. Let's push a seven. Now this is the end of our array. Now let's push another value. Let's say I want to push a nine. Well, we ran out of space. So what is our dynamic array going to do so far in memory over here, we have a zero of four and a seven. We previously talked about why we can't just allocate more memory right next to it. So what are we going to do? Well, we're just going to allocate a brand new array that will be able to contain all of the elements that we're trying to store. What I've done here, though, is take in the original capacity, the original size, which was three and multiply that by two. So now we have an array of size six, rather than size three. We're only inserting one extra element, though. So it would have been sufficient to just have an array of size four. So why did I double it? Well, we'll get to that. In a minute. So since we allocated a brand new array, we know it's going to go somewhere in memory somewhere random, but we don't really care where it is. Of course, it has to be a different location than where our first array is because this is still in memory so far. And what we're going to do is take all of the original values stored in the array. So over here, and we're going to copy them into the second array starting at the beginning. So if this is at index zero, well, it's going to be a zero. It's going to get copied to index zero in the second array. If this is at index one, it's going to get copied to index one. If this is at index two, it's going to get copied to index two. So our second array is going to look like zero for seven. So you can tell we solved the problem of not having enough space. Now we definitely have enough space for this nine to now also be here. So now our memory looks correct. We have all the values that we wanted. But the problem is we still have the original array. Do we really need this anymore? No, it's just taking up space, but we have all the values in the second array anyway. So now at this point, we deallocate this we free this memory. We basically tell the operating system. We're not using this anymore. You can use it to allocate different variables if you need to. So this doesn't exist anymore. So this definitely allows us to get around the fixed size property. So now if we add even more values to our array, which replaces the original array, we can keep doing that. Let's add a 10. Let's add an 11. Let's add a 12. If we add a 12, we're going to do the exact same thing that we did before, because we ran out of space. Now it's time to allocate a new array and we're going to make one that's a double the length of the original one. So size 12. And then we're going to insert the new element and we'll have a bunch of extra space to add more elements if we need to. But we might not need to. Now let's get back to one of the questions before why did we double this rather than just increasing it by one for the space that we needed for the original element. Well, notice how since we allocated a brand new array, we basically did a big O of n operation because first allocating the memory itself takes a big O of n where n is the size of the memory that we allocated. But regardless of that, we also had to take the original values from the original array and then move them into the second array. We had to push every single value. So that was also big O of n where let's say n is the length of the array, meaning the actual values that exist in the array. But what we're used to is pushing a value to the end of an array. In this case, let's say we push a value here, 10, that would have been big O of one. So what we notice is if we run out of space, yes, we can still add the next value. But it takes extra time because we have to create a brand new array, push all the original values into it, which is big O of n time complexity. That's the reason why when we create a bigger array, we are doubling the capacity every single time we're not just increasing it by one because we're finding a middle ground between not having to allocate a brand new array every single time. But also we don't want to have a bunch of empty space. We could have just created a super super large array with a bunch of empty space, right, like 90% of it could have been empty space, but that wouldn't have necessarily been good, because then we're taking up a bunch of memory from our operating system. And if we do it this way where we doubled the capacity, we get something called amortized complexity amortized time complexity. And what that basically means is yes, it took big O of n to add an element if we ran out of space. But we know it's going to be pretty infrequent when we run out of space. So we can still say that the amortized time complexity of pushing a value to a dynamic array is going to be big O of one, you can think of it as being the average time because we know on average, it's usually going to be big O of one, not big O of n because it's the vast majority of the time we add elements, it's going to be constant time, not big O of n. And there's actually a mathematical proof for why this is the case. In math, it has to do with power series. And I won't go too in depth into the math, but I will give you a high level explanation for why this is true. Let's say our goal is to push eight elements into a dynamic array, maybe the default dynamic array was only of size one when we allocated it. So let's say we add our first number five to the array. And so far we have an array that looks like this. Next we want to add a six to the array, but we know we don't have space. So what we really have to do is take this five, move it down to here and then insert the six over here. So I'm just counting the operations we're doing so far. We did one operation when we added this five here. And then to add the six, we actually had to do two operations where we moved the five and then added the six. Next, let's add the number seven. But for us to do that, we have to allocate a new array. And since we're doubling it every time, this array is of size four. So we're going to move the five here, we're going to move the six here, and we're going to add the seven here. So while we did three operations, we inserted three values here, allocating the array itself actually also took time complexity. So allocating an array of size four took four operations, we can say. And we're going to continue to do this. I'm going to add an eight over here. That's perfectly fine. We're going to add a nine here. We know that's going to require shifting all of these. And then let's say I add a 10 an 11 and a 12, which we do have space for here. So let's say it took us an additional eight operations to actually build this one. Now I'm oversimplifying a little bit because it actually took eight operations to allocate the space and then it took another eight operations to actually move each value into the array. But we're going to ignore that just for now. The main point I'm trying to get at, though, is to create an array of length eight, it actually took us eight plus four plus two plus one operations. But since we're doubling this every single time, this calculation is always dominated by the last term. What that means is the last term is always going to be greater than or equal to the sum of all previous terms. This is a math concept. And this is the reason why we're doubling it rather than just increasing it by one. But why is this actually important? Well, to create an array of size eight, let's say in this case, it took us 15 operations. We know that this number is dominated by the last term, which means that it's always going to be less than or equal to two times the last term. In this case, the last term is eight. But we know in the general case that it's going to be n for how many elements we wanted to push to an array. So we say that this is two times n. So in big O terms, we would say it's two times n. But with big O notation, we never care about constants when they're multiplying a variable. In this case, two times n can be simplified to be big O of n. We don't really care about constant values, at least when they're used in multiplication or addition. So finally, the result that we arrived at is pushing an arbitrary number of values to an array is big O of n time overall, even though sometimes when we have to exceed the capacity, we have to shift a bunch of values. But overall, it reduces to be big O of n, which is pretty much the same that we expected from our static arrays. So as long as we double the size every time that it's succeeded, we do have an efficient data structure when we use dynamic arrays. By the way, let me illustrate to you why we don't care about constants when we're talking about big O time complexity, we don't care about the difference between big O of two times n, or the big O of n, we don't care about any constant c that could be there, any constant, no matter how big it is, it could be 10, it could be 100, it could be 1000, we don't care about it. And again, it's because of math. Suppose this line is representing our n line. As the input size grows, the runtime is also gonna grow. But it's growing linearly, right? It's a straight line. But if we had a runtime complexity of n squared, now this is a two, but this isn't the type of constant I'm talking about, because this is being raised to a power of two, it's not being multiplied by two powers are definitely important. But we don't care about, you know, some constant multiplied by n, and we don't care about some constant added to n. It could be a different constant than this one, but we don't care about it. If it's added or multiplied, as you can see, n squared grows much more quickly than n. And that's the idea. Now for some smaller inputs, it might matter. Now with these, they do intersect at input size n equals one. But suppose we had a constant here, maybe we actually have a line like two times n, it doesn't matter what the constant is, because they are definitely going to intersect at some point. And probably in this case, it'll probably intersect at 1.4 or something like that. But the idea is they're going to intersect at some point. And after that point of intersection, the larger growing function is always going to be greater than the slower growing function. And that's what we care about.  That's why when we talk about big O time complexity, we don't care about constants, we care about how quickly is it growing? Is it big O of n, or is it big O of n squared? The same would be true if we added a constant. For example, this is what n plus eight would look like. Well, it gets a head start over the quicker growing function. But at some point they're going to intersect. And at that point, the quicker growing one is going to grow way faster. It's going to go off the charts, while this one still grows at the same rate. Now to summarize the time complexity for dynamic arrays is essentially the same as static arrays, we can still access the ith element anywhere in constant time, we can push and pop elements at the end also in constant time, even though in some cases we might have to resize the array, we still basically assume that it's a constant time operation for the reasons that I talked about earlier. And the good thing about dynamic arrays is we can do so, even if we don't have space because yes, we can allocate more space. The downside though is inserting into the middle or removing from the middle is still going to be a big O of end time operation because we're going to have to shift every value over. And there's no amortization for this. In the worst case, this is always a big O of end time operation. So now that we understand dynamic arrays, the next thing for us to do is understand how we can use them. There's a common data structure in programming called a stack, which typically supports three operations, you can push an element to the end of the stack, you can pop an element from the end of the stack, or you can look at the last element in the stack. Meaning in this case, we just read the last element without removing it like we would in pop. These operations should run efficiently. So pushing should be a constant time operation. Popping should be a constant time operation. And peaking at the last element should be a constant time operation. So do we need to design a data structure from scratch to be able to implement this? No, the dynamic arrays that we talked about earlier actually satisfy all of these requirements. So a stack can be implemented using a dynamic array. So typically when we're programming, we actually just use the default dynamic array that's given to us in the language that we're using. So remember, our stack is nothing but an array and we're allowed to push elements so we can push a one onto the stack, we can push a two onto the stack. And sometimes people like to think of stacks as being vertical. So when we say we're pushing onto the top of the stack, we're throwing a value in here and it gets thrown to wherever the top of the stack is since right now, it's empty, it'll go to the bottom. Now in reality, we would have some kind of pointer or we would maintain the number of elements that are added so far. So we would know exactly where to push the next element. let's push a two, it's going to go where the next empty spot is, which is now going to be shifted here. Same thing with the vertical representation. We push to the top of the stack, which is considered the end of the stack. If you're talking about a regular array and we can keep doing this, let's push a three. We can also now push a four. Even though technically we don't have space, we know our stack is implemented with a dynamic array. So we don't even have to worry about running out of space. We know it's going to end up allocating some more space for us anyway. So we don't even worry about that. Stacks are just one common use case of dynamic arrays, but we can also support popping elements. So when we pop, we can only remove elements from the end of the array, but we know that's efficient. So we're in this case popping from the top of the stack or the end of the array. Internally, we wouldn't necessarily delete this portion of memory. We would just say that this is now the new end of our array, or this is the new top of our stack and we can keep popping elements. Notice something about the way the elements are being inserted and removed.  So notice how the order that the elements were inserted in is the reverse of the order that the elements are removed in. In other words, the last element that was added to the stack is going to be the first element that's removed from the stack. The second to last element that was inserted is going to be the second to last that was removed if we pop all of the elements. So stacks are considered a life. Oh, data structure. That means that the last in is going to be the first out. There are many use cases for a data structure like this. The most obvious one is the one that we kind of implicitly just showed, meaning we had some sequence of values. In this case, it was numbers, but it could have been a string of characters like ABC. But the order that we added them in was the reverse of the order that we remove them in so we could use a stack to reverse a sequence if we wanted to, even though there are other ways of doing the same thing. There are definitely a lot of other use cases for stacks that can get a lot more complex. And as you solve problems related to stacks, you'll definitely notice this. We will continue to talk about stacks throughout the course. But if you want to practice using this data structure, you can find some stack practice problems in the practice section. Now let's learn about linked lists, which have a lot of overlap with arrays, but also a lot of differences. The first thing to know about linked lists is that they are made up of list nodes or sometimes just called nodes for short. A list node is an object that encapsulates two things at a minimum. These are the value of the list node. It could be an integer, a character. It could be another object. It could be anything. Maybe in this case, we have a four as the value. And also we have next, which is a pointer. This is going to tell us what is the next list node in the linked list. So this is essentially a way of connecting multiple list nodes together, which forms a linked list. If we just had a single list node, it wouldn't be very useful. In this case, let's say our next pointer points at null, which is another way of saying that it points at nothing. That means that in this case, we just have a single list node. That's not very interesting. So now let's understand how these nodes can be connected together. Let's first build a linked list. So first, I'm going to create one list node. The value I'm going to give it in this case is going to be a string. Let's call it red. And the next pointer is initially going to be empty. Or we could say it's by default set to null, so it's not pointing at anything. That means this list node is not connected to anybody yet. And we know when we create this object, it's going to go somewhere in memory. We don't necessarily get to control where it is, but we know it's going to be somewhere. We know that we're going to have a red node somewhere in memory, and it's not going to be pointing at any other node yet. Next, we'll create a couple more nodes. Let's say a blue node and a green node. So now that we have three list nodes, it's time to actually connect them together. Now, in most languages, the next pointer is actually a reference to another list node. That's how it's implemented. So in terms of code, this is what we could do. We could set list node one, assuming that's the name of our variable, our object that we created dot next, the next pointer to be list node two. So what that would do is take this pointer and basically tell it that the next node in the list is going to be this node. Now, what's actually happening under the hood at the lowest level is we have some address for our second list node, our blue list node. Let's call it X, X, and maybe this one is stored at address Y, Y. The way we know how to get to the second node is at the lowest level, maybe your language or operating system is doing this. The pointer tells it that the address is here. So that's how we know how to get to the second node. But usually, depending on the language that you're using, you don't have to worry so much about the address because the reference to that object is enough. So when we talk about pointers, we're usually talking about references to objects. But I'm mentioning this because as you can see here, the nodes are out of order in the way that we're going to connect them. We've connected our red node to our blue node, but the order in actual memory is the opposite. What this means is that linked lists are not stored in memory the same way that we use them as programmers. They could be in some random order in memory, but they're connected via pointers. So the red node is going to point at the blue node. And eventually we're going to have the blue node point at the green node. We could have some big mess like this in memory, but as programmers, we're going to have something nice and clean like this. So this is a difference from a linked list compared to arrays. Arrays are stored the same way in memory, but linked lists, as we can see, are not necessarily stored the same in memory. Next for us to connect list node two to list node three, we would do the same thing we have down here, except for list node two dot next, we would have a two here is going to be set to list node three. So something like this.  So now that we have an idea of how linked lists are stored in memory, we're not going to worry so much on the details of what's exactly going on under the hood. Now, what if we wanted to start at the beginning of our linked list and then loop through every single node until we got to the end? And we would know we got to the end, by the way, because our last pointer is not pointing at anything. Now, depending on the language that you're using, the code for that would look something like this, where first we have a variable called cur, we initialize it to be at the first node in the linked list. And we keep looping as long as our pointer current is not pointing at null. What that means is we have a valid linked list node. So let's walk through this code really quickly. Suppose this is our current pointer, it's pointing at the red node. That's how it's initialized. Then we go to the while loop statement. Right now it's not pointing at null. So then we're going to enter the while loop current is going to be set to next. So we're going to follow our next pointer over here, which is now going to be pointing at the next node. Very simple. Then we're going to go back to our conditional current is still not equal to null. So now let's set it to current dot next. So we're going to follow the next pointer, which is now pointing at the green node. So this is where our current pointer is now going to be. We're going to again check the condition. It's still not equal to null. So now we're going to follow the next pointer again, which in this case it is pointing at null. It's not pointing at any other node. So now our current pointer is going to be set to null. And then we're going to execute the conditional. And in this case, it's going to be false. So we're going to no longer execute the while loop and we're done with that piece of code. Now my question for you is what would have happened instead? If this next pointer of the third node was actually pointing at the first node? Well, we would have started here, then went to the blue node, then went to the green node, and then we would have came back to the red node and then back to the blue node, back to the green node and just kept doing that over and over again. It wouldn't be very fun to run because the program would crash. It's an infinite loop. But going back to the first case where we didn't have an infinite loop, what was the time complexity of going through the entire linked list? Well, it was the same as doing so with an array. It was big of N where N is the size of our linked list. So far, we've learned that link lists are pretty similar to arrays. Let's talk about a few more similarities real quick. As programmers, it would probably be helpful if as part of our implementation of the linked list, we're always keeping track of the head of the linked list and the tail of the linked list or the end of it. So let's assume that we always have pointers that can give us access to the first element and the last element. If we have a linked list of size one, suppose these didn't even exist. That means our tail pointer would be pointing at the same element as our head pointer. That's how we would know we only have a linked list of size one. But in this case, we have a couple more nodes. Suppose we now wanted to add a new element to the end of the linked list. And let's say we create a new node and its value is purple. Well, if we want to insert it at the end, conveniently, we have a tail pointer at the end of our current linked list. And all we need to do to add this to our linked list is just connect the pointer. So we would simply take the tail dot next pointer and set it to list node four, which is our purple node. So that would look something like taking this pointer and then instead connecting it to this one. But the problem here is that our tail is still pointing at the third node. We want to update our tail pointer now to actually be pointing at this one. And in terms of code, that's also pretty easy. We can set tail equal to list node four. We could also have set tail equal to tail dot next. Because remember, tail is still pointing at the third node and we know tail dot next now is set to list node four. So by setting tail equal to tail dot next, we're automatically setting it to this node. Can you tell me the time complexity of this operation? Well, it was a constant time operation. Since we already had a tail pointer at the last node, we didn't have to iterate through every single element in the linked list. We started all the way at the end and then we created a new node and then connected the pointers. It was just one operation that we needed to do, which is the exact same thing with an array. Now, let's say instead we wanted to remove a node. Removing any node in a linked list, whether we're talking about the end of it or the beginning of it, is also always a constant time operation. But there's a really big caveat. That's assuming we have a pointer to the previous node that we're trying to remove. So if we're trying to remove this node, we should hopefully have a pointer to the previous node. So if we're removing this node, what we would do is set our head dot next pointer. Instead of it pointing at the second node, we would set it to the next node that it's pointing to. So this is a little complicated because we're chaining the fields. Head dot next, remember, refers to this node. This node is equal to head dot next. And then if we say dot next one more time, we're following this pointer to the third node. So what we know is this evaluates to the third node. So when we say head dot next, which is this pointer is pointing at the third node, we're basically getting rid of this guy and taking this and setting it to the third node. Now, if we want to, we can free the memory that this node was taking up. But in most languages, we have garbage collection. So we don't really need to take care of that. The language and operating system will take care of that for us. We can assume that it no longer exists if there aren't any pointers pointing at it anymore. But this is sort of a benefit compared to arrays. We can remove any element from whether we're talking about the beginning or the end in constant time because we don't have to shift everything over like we did with an array. But in the general case, if we wanted to, let's say, you know, delete an arbitrary element in the linked list, we would first have to start at the beginning of the linked list and then follow the pointers until we found the element and then remove it. So practically speaking to remove an element, it can still take big O of end time if we have to search for the element. Now, so far we've talked about singly linked lists, but there's a slight variation called doubly linked lists, which can also be useful. The main difference as the name implies is that we have two pointers. We have double pointers. We have one pointer for the next node, the same for singly linked lists, but we also have a previous pointer, which is going to point at the previous node in the linked list. So with three nodes, one, two and three, the next pointers are going to be connected to the next node in the linked list. The previous pointers are going to be connected to the previous node in the linked list. Now, the first node does not have any previous pointers, so it's going to be set to null, we can assume, the same way how the last node has a next pointer set to null. That's how we know we get to the end of the list and this is how we know we've gotten to the beginning of the list. Now, just like with singly linked lists, let's assume that we have a head and a tail pointer to the first and last node of our linked list. Now, let's say we wanted to add a new node to the end of the linked list. It would be very similar to doing it with a singly linked list, meaning we would take the next pointer of our current tail node and assign it to the list node four. We would also want to set the previous pointer of this node to be at list node three. We would also want to set the previous pointer of list node four to point at list node three, because we want to make sure that this is doubly linked. We want to preserve the properties of our doubly linked list. And then we would take our tail and shift it to the new node that we just inserted. This is how the code for that operation would look like. We would first say tail dot next is equal to the new node that we're inserting. We're connecting the pointers, we're adding that node to our list. We're also connecting the previous pointer of that new node. The previous pointer should be set to the current tail. Remember, our tail pointer was originally pointing at node three. So that's what our previous pointer is going to be set to. But finally, in the end, we take our tail pointer and set it to the next node, which is going to be list node four from the assignment we did right here. The one thing to note is the order that we do these operations in is very important. We have to do this operation before we update the tail pointer. So now let's look at removing a node. Let's remove the last node from our list. And it's a little bit easier with a doubly linked list because we're allowed to look backwards. Assuming we only have a pointer to the tail, that's actually all we need. We don't need a pointer to the previous node because from our tail, we can follow the previous pointer and it's going to take us to the previous node. This is really convenient. With a singly linked list, we would have had to start at the beginning and then kept going forward until we got to the node that we wanted to be at. We would start at the tail, follow the previous pointer. We would be at list node two. We would take the next pointer of it, which is now pointing at list node three. And we would instead point it at null. And it's really that simple. Now we have a linked list of size two. Technically, this node still exists and its previous pointer is pointing here. But if we take our tail pointer and set it now to be here, as far as we're concerned, this node doesn't exist anymore. Technically, it does, but we have no references to it. So we're never going to see it ever again. And depending on the language you're using, garbage collection might delete this automatically for us. And the code for that operation would look something like this, where we create a variable called node two and we assign it to tail dot previous, which is going to be here. We didn't originally have a pointer to this node. So we created one by taking tail and getting the previous pointer. Now we're taking the next pointer of this node and setting it to be null. It's used to point at node three. Now it's not pointing at anything. That means that this is the new end of our linked list. So we should take the tail pointer and set it to node two as well. At this point, we have a linked, we have a doubly linked list of two nodes left. By the way, we did a few operations, but we didn't have to loop through the entire linked list. Regardless of the size of the linked list, this delete last operation is always going to be the same. It's going to be a constant time operation. So with doubly linked lists, we can insert a value at the end and we can remove a value at the end so we can do both of those in constant time. Doesn't that satisfy the requirements of a stack data structure? Yes, it does. That means that stacks can be implemented also with linked lists, just like they can be with arrays. But it's a lot less common to implement stacks using linked lists because with our original dynamic array, we could pop and push to the end of the array efficiently. But we could also access any arbitrary element of the array. This is a downside of linked lists, whether we're talking about singly linked list or doubly linked list because we can't just arbitrarily access the second element or the third element or the seventh element. We have to follow our pointers to do that. That means to access a random element of the linked list, it would be an O of end time operation. So if that's the case, it's probably better to use a dynamic array if we're talking about stacks because we get extra functionality that we lose when we use linked lists. So let's wrap up by reviewing the time complexity of linked lists and compare that to arrays. So remember accessing the ith element of an array, accessing any element at any arbitrary index is a constant time operation with arrays. Inserting or removing at the end is also efficient. We can push and pop efficiently. But inserting into the middle or removing from the middle is going to be a linear time operation because we might have to shift all of the elements over in either direction. Now with a linked list that looks something like this, accessing any element in the linked list is not necessarily going to be efficient. I mean, of course, if we already have a pointer to this node, for example, it will be a constant time operation, but that's not always going to be the case. If we had a really big linked list and we wanted to access any element in the linked list, in the worst case, we would have to start at the beginning of the list and then keep incrementing, keep iterating through the list until we got to that element. So linked lists are different. We can't just randomly access any element. The worst case time complexity is big O of N. But if there's a downside to linked lists, we can also expect that there's going to be an upside to them as well. Because that's the whole point of data structures. Some are better at certain things. Now inserting and removing at the end is the same as arrays. It's a constant time operation. We talked about that earlier. Inserting and removing from the middle, though, is a constant time operation. Remember, if we have a linked list that looks something like this, if we want to remove the middle element, we don't have to now shift everything over. We don't have to take all of these and then shift them over by one. All we have to do to remove an element like this one is take the pointer. It's currently pointing at that. But now we want it to point at the next one. That's all we have to do to remove from the middle. Inserting works very similar to that. So, yes, it's efficient to do that with linked lists, but the caveat and it's a really big one for us to remove any random element. First, we have to arrive at that element. We need a pointer to the element before we can remove it. So in most cases, we're going to have to start at the beginning, keep iterating until we find the element that we want to remove and then remove it. So while doing the insertion or removal is efficient, usually we have to iterate through the linked list before we can do that. So in most cases, it's going to be a linear time operation. So we can see that linked lists do have a slight benefit compared to arrays. But I'll be honest and say that arrays are much more common and much more useful for problem solving, being able to access the ith element, any arbitrary element very efficiently is really, really important, much more than something like this, especially when most of the time we do this, we're not actually going to be able to do it in constant time. We're going to have to iterate through the linked list. These are a couple of very fundamental data structures and I can't wait to show you even more. Next, let's talk about queues. Queues are another important data structure similar to stacks. The difference is queues follow FIFO, which means first in, first out. They support two operations, typically NQ and DQ, but different from a stack when we NQ elements, it's the same as pushing. So in this case, it's actually similar to a stack. When we push elements, we push elements to the end of the queue. That's called NQing. Now, DQing is removing a value, but instead of removing from the end, we're actually going to remove from the beginning. That's why it's first in, first out. The first element that we add is going to be the first element that we remove. Elements are going to be removed in the same order that they were added to the queue. And we want to do these operations efficiently. We want to be able to add to the end of the queue in constant time and remove from the beginning of the queue in constant time. We know we couldn't do that with arrays because if you remove from the beginning of the array, then you have to take every other element and then shift it over. That turned out to be a big O of end time operation. But with linked lists, we can achieve this. Let me show you how. So suppose initially we have an empty queue. So we'll have a current pointer, which is initially set to null. It has nothing. And then we add a value to our queue. Let's say we add red to our queue. Then we create a list node. And then our current pointer is going to be set to that list node because now we have one element in our queue. By the way, with this linked list, we will be maintaining a head and a tail pointer, which both are initially going to be at this node as of now. But we want to add another value to our queue. So we add another, in this case, blue to our queue. It's as simple as taking the next pointer of this node and setting it to the new node that we're inserting. At this point, our head pointer will be pointing at the first element here and our tail pointer will be pointing at this, which is our tail. That's how we know when we insert a new element like this one, we're going to take the next pointer of the tail node and then set it to the new node. This is really easy with linked lists, but now it's time to do the other operation, which is DQ, remove from the head of the list. Well, the good thing is it's as easy as taking our current pointer and setting it to be current dot next. Since our current pointer is at this node, dot next will follow the next pointer, which will be here. So it's as easy as that to take our current pointer and then point it to this node. And then if this is the beginning of our linked list, we can pretend like this doesn't even exist anymore. So DQing an element is very efficient. That's how we can do it in constant time, which you can't really do with arrays. But I do want to mention that technically it is possible to implement queues with arrays, but it can get a lot more complicated. It's much more simple to implement them with linked lists. Queues are a very commonly used data structure and will continue to use them throughout this course. Recursion is a very important concept for data structures and algorithms and we'll be using it throughout the rest of this course. It can be pretty difficult to wrap your head around. So I think it's best to introduce this topic as soon as possible. We're going to start with what I call one branch recursion. And we're going to do so using a math formula, specifically n factorial. If you're not familiar with it, the n factorial is a shorthand of writing n times n minus one times n minus two all the way until we get to the base number, which is one. So for example, to say five factorial would be to say five times n minus one, so five minus one, which is four, and then n minus two, which is three, and then keep a decrementing the number by one until we get to the base number, which is one. And then, you know, we do this calculation. It turns out to be 120. Now, you definitely don't need recursion to do this calculation. The easiest way to do it would be with a loop where we take this number and then decrement it by one and multiply it by the result until we get all the way down to one. But we can also do this with recursion and I think it's a good way to get introduced to recursion. Notice how five factorial is the same as five times four factorial because we know four factorial is going to be four times three times two times one, and we see that repeated over here. So another way of representing five factorial is to say five factorial is equal to five times four factorial. Or the general equation, which we've written up above, would be to say n factorial is equal to n times n minus one factorial. The reason it's important to understand it in this way is because recursion is all about sub-problems. We can see that it's not super simple to calculate n factorial, but we know it's going to be n multiplied by n minus one factorial. So we took a big problem and made it a slightly smaller problem. We call this the sub-problem, and this is why we're allowed to use recursion for this problem because we have a sub-problem. Now, I could show you what the code would look like to solve this recursively, and it's actually very short, but I think it's better to start with a visualization and then move to the code, which makes it easier. So suppose we're trying to compute five factorial. We know that the sub-problem is four factorial, n minus one, right? So we take five minus one, and we want to compute four factorial first. So suppose we want to compute five factorial. We know that the sub-problem we have to compute first is four factorial, and then we can multiply that by n, which in this case is five. By far, the best way to represent recursion is using a decision tree. In this case, we only have one decision. That's why I call this one branch recursion, but a tree is still helpful to visualize this. So before we can compute this, we have to compute four factorial. So in terms of code, this step would look something like this, where we have a function called factorial. It's going to take in some integer where we're going to compute the factorial of that, and then we're going to return the result, which is also an integer. Now, so far, we know that to compute n factorial, we have to solve the sub-problem, which is n minus one factorial. So we call the function that we're inside of, we call our own function. We call the same function. This is called the recursive step, but this isn't all we need. That's why I've left a little space over here. So let's continue with this and see what happens as we continue to solve the sub-problem. So we have four factorial. Well, again, we know that's equivalent to four times four minus one factorial. So we want to compute the sub-problem three factorial before we have four factorial. But the same applies for three factorial. It's equivalent to three times three minus one factorial, which is two factorial. So let's compute that. And again, same applies to two. It's equivalent to two times two minus one factorial, which is one factorial. Now, this is where we get to something different. Once we get to a one, that's the base of our series. That's the last term of the multiplication. So when we get to one factorial, that's equivalent to one. So that's what we call our base case. That means that for one factorial, we're not going to use this formula because we assume that one factorial is mapped to a constant, which is one. So we don't have to do this calculation because it would result in one times one minus one factorial, which is zero factorial, which in math is valid. Zero factorial would also map to one. But that's not so important for our case here. What's important here is that one factorial is when we can stop. So in terms of code, that would look something like this. If n is less than or equal to one, we can return one. The reason I say less than or equal is because of that zero case. If we were given zero as our original input, we would want to return one. That's just the definition in math. But you can see this is very important because if we don't have this, we would continue this infinitely. We would continue to call the same function that we're inside of. It would never stop. And we would never go back up to compute our original result, which we were trying to do was compute five factorial. We would never go back here. We would just keep going down and down and keep getting more negative and negative and negative. So how is this actually going to run? Well, let's say we were given five as the input. Five is not less than or equal to one. So we say that we're going to return five times four factorial. So that's how we go down here. We're going to go down a step to here. And then for four, we're going to see the same thing. It's not less than or equal to one. So we're going to compute three factorial. So we're going to keep going down and down and down until we get to one here. So that's going to be our base case. That's when this is actually going to execute. We're going to end up returning one. So we're going to go back up to our parent and have a one that we're returning. So at that point, this code is going to execute. We passed in two minus one factorial here. This return call evaluated to one and currently n is two. So this is going to be two times one. And then from here, we're going to end up returning two. So from here, we pop back to the parent and return two. So then this line is going to execute because what we passed into here was three minus one, which was two factorial. We know two factorial now is equal to two. That was the return value of this. So then we're going to call three times two and then return that that's six. So now it's starting to get a little interesting. We're going to return six from this line. We're going to return six back up to the previous call. So this, which was four minus one, which was three, three factorial is six multiplied by n, which in this case is four. So four times six is going to be 24. We're going to return 24 up to the previous call. And then we'll know that four factorial was 24 and in this case is five. So five times 24 is 120. That's going to be the result of the call, which is five factorial. So when we called factorial and passed in five, this is going to be the result. n is five. So five times 24 is 120. That's going to be our result. So when it comes to analyzing the time complexity, it can be difficult to determine just by looking at the code. That's why drawing a picture like this can be helpful. You can see that to compute n factorial, we basically have n steps. We have n calculations that we have to do n multiplications rather. So to compute this, the time complexity is big O of n, where n is, of course, the input that we're given. This is the same as it would be if we used a while loop or a for loop where we start with n and we decrement it by one each time to get this computation. So there's definitely no benefit in this case of actually using recursion. I'm mainly doing this to teach you and actually in this case, the recursive solution is actually worse than doing it with a while loop because in this case, we end up needing extra memory. This solution actually has big O of n memory complexity. We care about time complexity, but we also care about memory complexity. We'd rather not allocate additional variables that take up extra memory if we don't need to. Now, in this case, we're not even allocating any major variables. We don't have any arrays or linked lists or anything like that. So why is this taking up O of n memory? The way this code is going to run is similar to how I've drawn this picture. We're going to have a function that's computing this. That function is going to take up space in memory and it's going to we're going to save that. We're going to put that function on hold and we're going to say, OK, stay right there. First, we have to compute four factorial and then we're going to keep this in memory as well. We're going to save our spot here and we're going to say before that compute three factorial before that compute two factorial before that compute one factorial at the point where we're here, where we're calculating one factorial. We're going to have all five of these functions taking up memory. Now, each function doesn't really declare any major variables, but each function is going to have its own input parameter. So you can think of the function declaring one variable at the very least and the function itself actually takes up a little bit of memory so that it knows when this function is done, return back up to the parent. But that's getting a little too into the details. The important thing here is that we have n function calls that are all going to be alive at the same time. So this takes O of n memory. And by the way, the non recursive solution would look something like this, where we just have a single variable. Let's call it our result or our factorial. It can be initialized to one because we know that's going to be the base case anyway. I don't think negative factorials are something that we actually have to consider. So we're going to assume that n is always greater than or equal to one. And then while n is greater than one, we would multiply the result by the value. So n and then decrement it by one. So then we would get, you know, n minus one and minus two until n is equal to one. And then we would stop. Now let's look at the more interesting case of two branch recursion. And let's use another math example. In this case, let's calculate the Fibonacci numbers. Now, the general formula to calculate the nth Fibonacci number is to take the n minus one Fibonacci number and the n minus two Fibonacci number and add them together, which gives us the nth Fibonacci number. But if we do it like this, we're going to go on forever if we try to calculate the fifth Fibonacci number, because when do we know we can stop? Well, we do have some base cases for us to find the zero Fibonacci number is zero. The first Fibonacci number is one. So using this, what would the second Fibonacci number be? Well, it would be the n minus one Fibonacci number, which is one plus the n minus two Fibonacci number, which is zero. And we know that these are defined as a part of our base case. This is one. So one, this is zero. So plus zero. That means the second Fibonacci number is equal to one. So now we have that, then we can compute the third Fibonacci number, which we know is going to be n minus one. That's two plus n minus two. That's going to be the first Fibonacci number. So now we have the second Fibonacci number, which is one. We have the first Fibonacci number, which is also one. So this is equal to one plus one. So therefore the third Fibonacci number is two. Now, the way I'm calculating it right now is very straightforward. I'm pretty much looping through these and we could go as high as we want. We could now calculate the fourth, the fifth, the sixth Fibonacci number. But this is not recursion. The recursive solution for this problem is actually less efficient. But I still want to show it to you because it illustrates for us two branch recursion. So let's say we want to calculate the fifth Fibonacci number. This is where our decision tree is going to get very useful. Maybe we can't immediately compute this, but we know this can be broken up into a couple sub problems like n minus one and n minus two. So to compute the fifth Fibonacci number, we can compute the n minus one, which is four and n minus two, which is three. But for either of these branches, we still haven't reached the base case yet, which we know is zero or one. So let's continue down the left path. This can also be broken up into a couple sub problems. Again, n minus one and n minus two. So n minus one would be three and minus two would be the second Fibonacci number for this, it's going to be n minus one, which is the second Fibonacci number and n minus two, which is the first Fibonacci number. Now let's continue to draw this out. So the third Fibonacci number can be broken up into n minus one, which is the second Fibonacci number added with the first Fibonacci number to get the second Fibonacci number. We can get the first Fibonacci number added with the zero Fibonacci number. It's starting to get a little bit messy, but we're almost done. So over here, the second Fibonacci number, which we sort of just did over here, is also going to have two steps, which is the first Fibonacci number added with the zero Fibonacci number. Now over here, do we also need to break this up into sub problems? No, because we finally reached our base case over here. So now to take a quick preview at the code, the base case we know is going to be either zero or one. So we could have an individual case for each of these. We could say if n, the input is zero, then return zero. And if it's equal to one, return one, but we can condense that into a single if statement, if n is less than or equal to one, that means if it's either zero or one, then return n, because when n is equal to one, we're returning one, when it's equal to zero, we're returning zero. So whatever it is, that's what we can return when it's less than or equal to one. But for the recursive case, as we've been doing, we know we have to compute the n minus one and the n minus two Fibonacci number. And then when we have those, we're finally going to add them up and then return that integer value. But we're not quite done yet. We know that this here, the first Fibonacci number, it is one. So that's what I'm going to put here. And actually, we've reached the base case with all of these, but there's just one branch left for us. So let's quickly complete that one and then we can compute the result. So the second Fibonacci number we know is n minus one, which is one plus n minus two, which is zero in this case. So adding these together will give us the second Fibonacci number. So now going down this path, let's say for n minus one, we're going to end up returning one in our code over here for n for zero. We're going to end up returning zero. And then we're going to be back up here in our decision tree for this. The code we're going to be at is this return code. We've computed n minus one, which turned out to be one. We computed n minus two, which turned out to be zero. Now we're adding them together one plus zero. So we're going to end up returning one from here. And this was also a base case. So recursively here, we would have executed this line of code and we would have ended up returning one. You can see that it might not be easy to know what's going on just by looking at the code, especially when you get to two branch recursion and beyond that. That's why we draw out these decision trees, which make it relatively simple. So we know to compute the third Fibonacci number over here, we get the results of the two paths. We were first computing the second Fibonacci number was turned out to be one and the first Fibonacci number, which turned out to be one as well. We add those together. So we add the return values from here and then we return two from here. So now we're trying to compute the fourth Fibonacci number. First, we needed to compute the third Fibonacci number to do that. We did that here. Now we need to get the second Fibonacci number and to get this, we get its sub problems, the first and the zero Fibonacci number, which both are, well, this is one and then the zero is zero. We add those together. That's going to be one. So from here, we return one. So to get the fourth Fibonacci number, we have two, which is the third Fibonacci number and one, which is the second Fibonacci number. We add those together and we return three. Now at this point, you're probably starting to get the idea. So finally, to get our original result, which is the fifth Fibonacci number, we needed to compute the fourth Fibonacci number. We did that. We have three. And now we need to compute the third Fibonacci number. And to do that, we need to get the second and the first Fibonacci number. And to get the second Fibonacci number, we need to get the first and the zero, which are going to be one and zero. Add those together. We get one as the second Fibonacci number. Add this and this together. We get two as the third Fibonacci number. And then add this and this. We get five to be the fifth Fibonacci number. It's gotten very messy here. But we did finally get our result. And again, this is definitely not the most efficient way to solve this problem. Earlier, we were doing it with a loop. So to get the Nth Fibonacci number with the loop technique I was talking about, the time complexity would be big O of N. But here we've drawn it out recursively. And clearly this is not big O of N. So to analyze the time complexity of this recursive solution, looking at the code is not going to help us a ton. The picture is a lot easier to use, but it's going to require a bit of math. First, to get the fifth Fibonacci number or just some general Nth Fibonacci number, we have to break that up into two sub problems, right? And then those two sub problems have to be broken up into two more sub problems each, and then those sub problems might need to be broken up into two more sub problems unless, of course, we've reached the base case, which for this one, we have reached the base case. But in general, for each of these, we might have to break it up into two more sub problems. Now, the fact that we have to break it up into two sub problems comes from the fact that we have two branches in our recursive tree. But in this recursive tree, how many times are we going to have to break it up into two steps? In other words, what is the height of this decision tree going to be? The height is basically how many levels does this tree have? You can see one, two, three, four, five levels. That makes sense because for the path that where we have five, then we have four. And then to get that, we have to go to three, then to two, and then to one. That's what's the longest path is going to be. So the number of layers in this decision tree is going to be n, where, you know, that's the nth Fibonacci that we're trying to compute. Now, this is the part where I could get overly technical if I wanted to, but I want to try to keep it simple in terms of math. So in general for this, for us to get the number of Fibonacci values in the last level, theoretically with math, it would be we start with one and then we double every time. So in theory, it'd be two times two times two. And the number of terms that we would have is equal to n. Roughly speaking, it's equal to n because that's the height of the tree, right? If we're taking this and then doubling it and then doubling it, the number of times we double it is going to be n. And that's the same as the input value. So to get the number of values in the last level is going to be roughly, let's say two to the power of n. Now, in this case, we can see that the last level only has two. So in reality, this is actually an upper bound for the number of values we could have in the last level. It's not the precise value. It's an upper bound. But what we know about this last level is the same thing we talked about earlier in math, when you have a series like one and then two and then four and then eight, where you're doubling it every time. This is special in math. It's called the power series. It's always dominated by the last term. So eight is going to be greater than or equal to all the previous ones combined. If we add a value 16, it's going to be greater than or equal to all the previous combined. So what I'm saying here is that this is an upper bound for the last level. That means it's also an upper bound for the total number of values in this decision tree. If you don't believe me, well, remember, we can multiply this by any constant. So we say, let's say our constant is two. So two times two to the power of n is still in terms of big O time complexity equivalent to two to the power of n in terms of big O time complexity. Precisely, though, it would be n plus one. But remember, we don't care about constants when they're multiplying or adding to variables. So two to the n plus one is equivalent to two to the n minus one as well. Right. In terms of big O time complexity, all three of these are equivalent. So this is essentially a long explanation for saying that two to the power of n is how we can bound this in terms of big O time complexity. Even though this isn't the precise number of values in this decision tree that we drew, it's still a very good upper bound because remember, we don't care about constants like plus one or minus one. And this idea of two to the power of n is something we're going to continue to see throughout the course. It all comes from that idea of math, from that idea of power series to turns out to be a very special number for computer science and math. Next, let's move on to a very fundamental topic, which is sorting, and we're going to start with the insertion sort algorithm. Sorting is used all the time, and there's a ton of different sorting algorithms, all with their own trade-offs. It's usually applied to arrays like this one, but you can also apply it to other data structures, including linked lists and others. So in this case, we have an array of five values and clearly they're not in order. They're not in ascending order, which would be an increasing order like one, two, three, but they're also not in decreasing order, which in this case would be six, four, three, etc. Suppose we want to sort them such that they are in ascending order. So our target array would look something like this, one, two, three, four, six. We can achieve this with the insertion sort algorithm. Let's see how we can do it. Well, the main idea is to break the problem into sub problems again. So if we want to sort the entire array, the first thing would be to have the first portion of the array, meaning just the first element have this sorted. Well, one value like two is sorted by default. I mean, how could this be not sorted if it's just one value? So we consider any array of one value to be sorted. The next thing to do, the next sub problem would be to sort the first two values, make sure these are sorted and then have the first three values sorted and then have the first four values sorted and keep doing that until we have the entire array sorted. So thinking of it this way in terms of sub problems makes the algorithm a lot more simple. Now, since we are doing it with some problems, technically, if we wanted to, we actually could solve this using recursion, which is a technique we just learned, but it's not really useful in this case. So I won't do it. We can do this without recursion, AKA we can do this iteratively. We can have an iterative solution, which is using loops. Now, the idea is we're going to loop through the array, but we're going to start at the second element because we know that this sub array is already sorted. So starting here and assuming that every value before this position, meaning this sub array is already in sorted order, our goal now is to have this array be sorted. So our goal really is to figure out where to put this value. We already know all of these are sorted. Where should we put this one in terms of this array? In this case, we don't have a lot of choices. The logical thing to do is compare this value to the only other value in our array. Is this larger? If this is larger, then it should stay where it is. If it's smaller, it should be swapped with the value over here. Since this is larger, it can stay here. Now, there's the other edge case where what if both of these are equal? If that's the case, this value can also stay here because it doesn't matter whether this goes here or here if they are both equal because it'll be sorted either way. This is for ascending order, but it would work the same way with descending order as well. So now that we know where this value should go, it should stay where it is. We can now move to the next value. So by the time we get here, we know that this sub array is already sorted. So at this point, we're going to do a similar comparison. We're going to compare this to its left neighbor is for greater than three. Yes, it is. So it's going to stay exactly where it is. And at this point, we didn't even compare four to two, but we don't need to. Do you know the reason why? Well, we already know these were in sorted order. So if four is greater than three, of course, it's going to be greater than every value to the left of three, because these are sorted. Every value to the left of three is going to be less than or equal to three. And now every value to the left of four is going to be less than or equal to four. So at this point, we know that these values are in sorted order. We can shift our pointer to the right by one over here. And now things are going to get a little bit interesting. So now we have this sorted portion and we have to figure out where the one should go, should it go at the end of these three values, should it go in between these two values, should it go in between these two values, or should it go over here? Well, let's see what the algorithm does. This is why it's called insertion sort, because we're taking one value and inserting it into a sorted array. So let's see what the algorithm does in this case. First, we're going to compare one to four is one greater than or equal to four. It's not. So now we finally execute the other case. And by the way, the pseudocode for this would look something like this. Remember our pointer, which is I in this case started at index one, and we're going to keep going until we've reached the end of the list. So that's pretty straightforward. And now we're going to get to the interesting part where we compare this to the neighbor. So we have a second pointer for the neighbor we call that J. This is at I, or you could also call this J plus one. That's what we're going to be doing. And then you compare these. And now the value at J plus one is less than the value at J. That's this part of the code. This part is basically to make sure that we don't go out of bounds. And you'll see what I mean in just a second. But now that this comparison holds, we're going to perform the swap. This is where we take this value and move it over here and take this value and move it over there. So the first thing we would do actually is take the value that was originally at J plus one, which is one and put it in a temporary variable. Because what we're going to do is now at this index J plus one, we're going to move the value that was here. So we're going to put a four over here and then over here. Now that we've lost the one, we have to use our temporary variable. So we're going to put a one over here from our temporary variable. And originally, our J pointer was over here. We're going to decrement it by one, which means we're going to shift it to the left by one over here. And the reason this is a while loop and not just an if statement is because now we're going to continue this whole process. We originally had the one over here and we know it should be shifted to the left because it's definitely less than four, but we don't know that we're done. We don't know that this is the final spot that this one is going to be. We have to continue comparing to the left neighbors. So now we're going to execute the condition again. First, we're going to make sure that J is not out of bounds yet, because as we keep shifting it, we know at some point it's going to be all the way over here. It could be out of bounds. But right now it's not out of bounds. We know that because it is greater than or equal to zero. And now we're going to compare the value at J plus one to J. J plus one is less than the value at J. One is less than three. So now we're going to do the exact same thing. We're going to perform the exact same swap. So now we have our three over here and our one over here, but we're not done yet. We're going to decrement our J one more time. Now J is going to be over here. It's still in bounds and the value at J plus one is again less than the value at J. So now we're going to do another swap. So the two is over here and the one is going to be over here. And now J is going to be shifted to the left by one again. Now it's out of bounds. So now there's no point in even doing a comparison. That's why we're checking that it's in bounds before we do this. We don't want an index out of bounds error. So since it's not in bounds, we we can stop doing this loop. And we know now that our eye pointer, by the way, was over here. So now at this point, our eye pointer is going to be shifted over here because we're going to execute the next part of the for loop, the outer loop that's over here. And we know because of that, this portion of the array, these first four values are now in sorted order and they look sorted as well. One, two, three, four. So now that our eye pointer is over here, our J pointer is going to be initially over here, J is in bounds. So now let's compare the two values is six less than four. It's not so we know that this is greater than four. Therefore, it's going to be greater than all of these as well. So that means that this is already in sorted order. Our outer for loop is now going to stop because there's no more elements over here, you know, left for us to traverse. Now, we've been talking about sorting integers so far, but of course, this could be applied to characters if we had something like B, C, A, as long as we have a way to compare characters. So in this case, let's say we're sorting based on just alphabetical order, we can basically sort any set of values as long as we have a way of comparing two values together. So in this case, we could sort these to be something like ABC. Of course, we could also sort strings themselves the same way a dictionary sorts words. So a word like Apple would go before a word like banana with sorting. There's also this notion of stable versus unstable sorting. Let's say we had this array of values, seven, three, seven. Any sorting algorithm is going to take these values and put them in sorted order, which would be three, seven, seven. Any sorting algorithm could do that, but the difference between a stable sorting algorithm and an unstable sorting algorithm is this. This is what a stable sorting algorithm would do. It would put the numbers something like this. The thing to notice here is that for seven, it appears twice in the array. So this first seven could have gone here and then the second seven would have gone here, or they could have been in reverse, right? This seven could have gone first and then this seven would have gone second. Both of those are valid sorting order, but a stable sorting algorithm will preserve the original order when there's a tie. We know that there's two sevens. And for some reason, if we wanted the original relative order of these two sevens to be preserved, meaning this one showed up first before this one. So it should go first in sorted order. That's called stable sorting. Unstable sorting might achieve this, but there's no guarantee. It's not necessary that that will be preserved. So it could have flipped them for some reason. We'll touch on this again as we continue. But my question for you, based on this, do you think the insertion sort algorithm is stable or is it unstable? But well, let's quickly go through how it would execute on this. First, our pointer would be over here. We would compare the three and the seven. They're out of order, so we would swap them. So then our our first two values would look like this. So that's good so far. And then our third pointer would be over here. Right. And this would be a three and this would be a seven. And we would say this seven is it less than the seven on the left of it? Right. That's where this would execute. This seven is not less than that. So it's going to stay exactly where it is. So therefore we would achieve this output where the relative order in case of a tie would be preserved. These two would stay in the order they were in originally. So based on this implementation, this is a stable sorting algorithm. It's preferred to keep an algorithm stable if you can. We could code this in such a way where it's not stable, but that would have no benefit for us, so we're going to keep it as stable. So now finally, let's talk about the time complexity, which is interesting for insertion sort, actually. And the best way to actually understand it is to look at a couple examples. Let's say we were running insertion sort on a list that's already sorted. What would the algorithm do? Well, we would have a pointer over here. We would want to, of course, iterate through the array. But but then we would do a comparison from here. We would compare it to the left neighbor. They're already in sorted order, so we don't have to do anything. We can shift our pointer over here. We compare these two values. They're already sorted. We don't have to do anything. We shift the pointer again. Then we compare these two values. They're already sorted. We don't do anything. We shift the pointer. We're out of bounds. That means we're done. So as you can see, when we have an array that's already sorted, we run insertion sort and the execution is just iterating through the list, which is big O of n time complexity. Of course, we have nested loops here, but just because we have a loop here doesn't mean it's necessarily going to execute. I just showed you an example where this inner loop is never going to execute. So in this case, the best case time complexity is big O of n. Now, technically big O means worst case, so I'm kind of misusing it here. But it's kind of common for people to talk about it this way. But in this case, I'm saying the best case time complexity, which would occur when the input is already sorted, is going to be linear time complexity. Let's look at the other case, where is the worst case time complexity, which would actually occur on the opposite example where the input is in reverse order and we want to sort it in ascending order. So in this case, again, we would loop through the array. We would start here. We would compare the two neighboring values. We would see that they're out of order. So then we would have to swap them. We would put the three over here and the four over here. Then we would shift our pointer over here and then we would compare these two values. And then we would see they're out of order. We'd have to swap them again. We would have to put the two over here and the four over here. And at this point, we're still not done yet. This two is going to be compared to its left neighbor now. And they're again out of order. So we would have to put the three over here and the two over here. So you can see it's definitely getting messy. But ultimately what we would find is we would have to take this three, shift it over here, then we would get our pointer over here. This two, we would have to shift it here and then we would have to shift it here. Then when we get to this one, we would have to shift it to the left, then shift it to the left again and then shift it to the left again. So for every single value that we iterate through, the inner while loop would have to execute the maximum number of times until that value is shifted all the way to the left. When we get to the two, we'd have to shift it all the way to the left. When we get to the one, we'd have to shift it all the way to the left. Now, for an input size of four in this case, n squared time complexity would look like four squared because the length is four, which would be something like four plus four, right? Added together how many times? Well, four times. That's just the math formula here. But this isn't that. What we were doing right now was actually a bit different. What we actually have is something like one and then plus two and then plus three and then plus four, because for this value, we might have to consider it to be in these two positions. For this value, it could be in these three positions. For this value, it could be in these four positions, which correlates to that four. And I just talked about the two and three case. And we might not have a one case because remember, we're skipping the first index. But again, this is just an approximation. And that's enough for us when we're doing big O time complexity. Now, what most people do when they have nested loops, they automatically assume that the time complexity is big O of n squared. And usually it's the correct assumption, but I bet most people don't know why that's the case. And I'm going to explain it to you briefly right now. This equation is bounded by n squared. It's pretty obvious when you look at it like this, because every term here is greater than or equal to every term here. But I'm going to show it to you in terms of big O time complexity, where remember, we know that constants don't matter when we're multiplying by a variable. So some constant C times n squared doesn't matter regardless of what the constant is. I'm going to use this idea to prove it to you that this is bounded by n squared. And I'm not even going to use a math proof.  We know that n squared, where n is four, would look something like this in terms of geometry, right? Four times four, right? This is us having to iterate through an array of size four, four times we have to do that. We have to iterate through it once, twice, three times, four times. But we also have the case where we iterate through just, let's say, the first value of the array and then the first two values of the array and then the first three values of the array and then the first four values of the array. So maybe now it's becoming a little more obvious why this is bounded by this. And not only that, this is actually pretty much exactly half the size of n squared. And we even talked about how the first term in this case doesn't actually apply. So maybe this isn't even there, but it's still you can see approximately half the size of n squared. We didn't even use a math proof to figure this out. This is obvious enough from looking at a picture. So if this is half the size of n squared, we can write it as n squared divided by two, or in other words, one half times n squared. And this is just a constant, remember, and we don't care about constants. So we can say this, or in other words, iterating through an array like this would be the same as big O of n squared time complexity. That's the worst case time complexity of insertion sort. So that was a lot to cover. But to finally wrap up our first sorting algorithm insertion sort, which is a stable sorting algorithm has a worst case runtime of n squared. But it's also worth mentioning that the best case runtime is big O of n. That's not always true for other sorting algorithms. But it does turn out that there's better sorting algorithms than n squared worst time complexity. Merge sort is one of the most common sorting algorithms and for good reason, it's a pretty efficient algorithm. The main idea is to take the input array and then split it into two approximately equal halves and then for those halves split them into approximately equal halves and then continue to split each sub array until we can't split them anymore, which would mean we have individual elements left for us to then sort. The idea is to break up the original problem of sorting the entire array into sub problems. So in order for us to sort the entire array first, we can sort the first three values three, two, four, so we can sort the first half of the values. In this case, we have an odd number of values, so we can't split it exactly into half, but more or less, it's approximately half. And then the second half of values, we want to sort these as well. But then for these sub arrays, we also have sub problems. We can split this array into half, the first half and the second half and sort those portions of the array before we sort this original array. And the same thing for here, you can see that since we have a natural way of splitting this into sub problems until, of course, we reach the base case where we just have sub arrays of a single element like down here as well. This problem naturally lends itself to recursion. I promised you that recursion was going to come up a lot more. And this is one of those cases. And this is clearly two branch recursion because we're splitting this into two halves, and I'll talk later why exactly we're splitting it into halves. But to give you a hint, as you know, the number two is pretty important. And as we take the array and divide it by two each time, that lends itself to be an efficient algorithm. We'll talk about that more a little later. But this array as well is being split into two halves, two branches. This array, same thing. But these are the base cases. Now, we talked about how we're going to divide this into sub problems. By the way, the technique we're using right now is sometimes called divide and conquer because we're taking the original problem and dividing it into sub problems and then solving those sub problems before we solve the original problem. But I haven't talked about how we're even going to solve these sub problems and what we're going to do once we have that done. Well, let's start on the left side. We're going to first take this array, get the left half of it. We're going to take that and get the left half of that. And then we're going to take this and then split it into two individual elements, three and two. Now, this is technically a sorted array and this is technically a sorted array. When you have two sorted arrays, we can merge these two arrays back into the original array such that they are in sorted order. That's why this is called merge sort because we break it up into two sub problems and then merge them back together. So forgetting the original values that were in the array, we create a copy of the value that was here and we create a copy of the value that was here. And in this case, it's pretty simple because we just have two elements. So we're going to compare these two. Which one is smaller? Two is smaller. So the two is going to go over here and the three is going to go over here. Now, from the perspective of this array, we've solved the left sub problem. We have this portion sorted. Now we need this portion sorted. Well, it's just a single element. So this is the base case. So now we don't care about the original values that were over here. We have two sorted arrays and we want to merge them together into the original array. In general, the algorithm is going to be two pointers for us to do that. We're going to start at the beginning of this array and we're going to start at the beginning of this array and we're going to compare the values because we know at the beginning of each array is going to be the smallest value because this is sorted and this is sorted. So we're going to compare the two values. Which one is smaller? Two is smaller than four. So two is going to go over here. The pointer that was over here is now going to be shifted to be over here. And now we're going to continue the algorithm. We're going to compare the value here to the value here, which one is smaller? Three is smaller. So the next value that we insert is going to be three in the next position of this array. And at this point, our pointer that was in the first array is now going to be out of bounds. So at this point, we have no choice but to place the value from the second array in the next spot, which is also the last spot. So we put the four over here. So now we finally arrived back at the original problem we were trying to solve. We sorted the left half of the array. Now it's time for us to sort the right half. So then we have this portion. We break it up into individual elements. We don't care about what's originally here. We compare these two values, which one is smaller? One is smaller than six. So we put a one here. That is what the original value actually was. And we put the six here. So in this case, the original was already in sorted order, but we still had to do this work anyway. But now that we took the original array, have it sorted into a left half and a right half. We can merge these two portions together to make the original array sorted. So forgetting about the original values that were over here. We again use our two pointer technique. We have a pointer at the beginning of the left array and a pointer at the beginning of the right array. We compare the values. One is smaller than two. So we're going to take the one, put it at the beginning, and then we're going to shift the pointer that was here to be over here. By the way, we are going to have a third pointer in the output array. It's going to tell us where we should insert the next element. Originally, it's over here. Now that pointer is going to be over here. And then next, it's going to be over here and then here and then here and keep going until we run out of elements to insert. But right now we're going to be comparing the two and the six, which one is smaller, the two is smaller. So we're going to insert the two over here. We're going to take the pointer that was at the two and then shift it to the right to be over here. And we're going to repeat which one is smaller, three or six, three is smaller. So let's put the three over here and then shift the pointer to be at the next element. Let's compare these two again, four is smaller. So we put the four over here and then shift our pointer to be over here now. It's out of bounds. So we have nothing left to compare this six to. So at this point, whether we have one element over here or maybe we would have a couple more elements over here, regardless, since we ran out of all elements of one of the arrays, at this point, we would just fill in the remaining spots from the other array that's non empty. So in this case, we only have a six. So we put the six here. But if we had more elements like a seven and an eight, we would just start filling them over here. So taking a quick look at the code, like I said, this is going to be a recursive algorithm clearly where we're breaking it up into two steps. So this is going to be two branches of recursion. Now, into this merge sort function, I'm passing in the starting index and the ending index, as well as the array that we're actually going to be sorting. That's because as we break this up into sub arrays, we don't necessarily have to create a variable for each sub array. We can just kind of keep track of this half based on the starting index and the ending index rather than actually creating a brand new sub array like that. But how do we know if we've reached the base case? Well, if the length of the sub array is less than or equal to one, well, how do we get the length itself? We can take the ending index minus the starting index plus one. So basically, you know, this element by itself is at index zero. So what we do is take the ending index, which is zero minus the starting index, which is zero plus one gives us one. So this is of length one. So that's how we know it's a base case. That means it's already sorted so we can just return the array itself. But if we got to a case like this one where the starting index is zero and the ending index is one, then we're going to get the ending index minus the starting plus one, which is going to give us a length of two. That's correct. This is length two. But that means our length is not less than or equal to one. So what we have to do is calculate the middle index between these two. So we take the starting plus the ending and divide it by two. So zero plus one divided by two. So most programming languages will round down. That's what we want to do round this down. So one divided by two is going to evaluate to be zero. So we're going to say the middle index is zero. This is the middle index. So what we're going to do now is break this up into two halves. We're going to call merge sort from starting to middle. So in that case, this means call merge sort on the array starting at index zero and ending at the middle index, which is zero as well. So we're going to call basically that evaluates to this. We're going to call merge sort on just the first element. And we're also going to call merge sort on the second half of the array. So from index M plus one, which is one and the ending index, which is also one, so, you know, that's pretty much correct. We're going to call merge sort on this portion of the array. And these, of course, are the base case. So after we call merge sort, we're going to expect those two halves to be sorted. So then what we're going to do is merge those halves together. Now, I haven't shown you the implementation of this. It's not super complicated. It's just a decent amount of code. It's basically the two pointer technique we were talking about a moment ago. But what we're saying with this function call is merge the left half of the array, which starts at index S and ends at index M and merge that with the right half of the array, which starts at M plus one and ends at index E. So it will basically merge these two together into the original two element array. Now, I will say when we do merge the left and right half together, we do need to create extra memory. So for the left and right half array, we're going to create temporary arrays. So we are going to create copies of the left and right half arrays, but we're only doing that for the merge step. So only when we start to actually merge them together into the original are we going to create those copies so that we don't lose what the original values were. So in general, we start out with a big problem. We split it into two sub problems, solve the sub problems and then merge the result of the sub problems together. Now, in terms of time complexity, this is a relatively efficient sorting algorithm because we're splitting it into halves, we're doing that on purpose because it does make things more efficient. So the first question is starting with an array of length N, how many times can we split it by half? In other words, how many levels are there to this recursion? Because it's going to be the same number of times where we can take N and divide it by two because here we have let's assume actually we just had four elements to keep the math simple, we would have four elements, we would split it into two elements on each side and then we would split it into one element on each side. And these two wouldn't exist. I'm doing this just for simplicity, but we start with N equals four. We divide it by two. So N equals two. And then we divide it by two until N equals one. We know when N equals one, that's our base case. So what's the math formula for how many times we can take this number and divide it by two until it's equal to one? Well, if we were starting at one and then multiplying it by two every single time, that would be something like two to the power of N, but we're doing the reverse of that. We're dividing it by N. So what we're asking is we have a number N and we want to divide it by two and then divide it by two and then divide it by two, which is the same as saying two times two times two, et cetera, et cetera, right? Which is the same as saying two to the power of some variable like X, right? This is the number of times we're going to divide this by two. And we want to keep dividing it by two until it's equal to one. Well, by doing a little bit of algebra on this, we can rearrange this to be the same as N equals two to the power of X. We care about X. That's how many levels are going to be in this merge sort algorithm. So how do we solve for X? Well, in case you forgot a little bit of math, I'll tell you we can take the log of both sides of this equation. That will give us, and by the way, I'm doing log base two. Log base two of N is equal to log base two of two to the power of X. And if you forgot your log operations, this can be simplified to take this X away and put that X over here. Now, log base two of two is the same as saying two to the power of what is going to be equal to two, while two to the power of one is equal to two. So this whole thing, log base two of two, simplifies to be one is what I'm getting at. So what I'm saying is we already solved for X. X is equal to log base two of N. So what I'm saying is if we have a number N equals four or any number, how many times can we divide it by two until it's equal to one? Well, our answer is log base two of N log base two of that value is how many times we can divide it by two until it's equal to one. And this turns out to be a reoccurring theme throughout algorithms and data structures. It's something we're going to see a lot more throughout the course. And this is kind of the math background of why most people don't touch on this and most people never learn it and never understand it. But I wanted to explain it to you because I think thinking about it this way and understanding your thought process is very important throughout algorithms and data structures. It's really what separates beginners from people who can solve problems on their own. So we did all that work just to figure out that the height of this is going to be log base two of N. I'm going to usually omit the two. Usually it's implied that logs are based to most of the time. But that's not the entire time complexity. That's the number of steps that we're going to have. But what's the time complexity of each step of this algorithm? Well, it's big O of N. Let me tell you why. Basically, it has to do with this merge step. So suppose we're at this step of the recursion. We have our sub problems here and here. And now we want to merge them together in this array. What are we going to have to do? We're going to have to iterate through every element in each of the sub arrays, which is going to result in an element being put in each spot in the original array. So basically for this step, we're going to have to iterate through every position of the input array. So that's clearly an O of N time operation. But my argument is we're going to be doing that for every level in this recursion. So here for this sub array, we're going to split it into a couple of smaller ones and then merge these into this array. But this is only half of this level, right? To do this part of the level, we're going to have to do the same thing. We have an individual element here and here. We're going to merge these together into the original array. And so this level to build this level took O of N. And similarly for the bottom level, it's the base case, but we still have to visit this right like one operation is still going to run for this part. And then same for this and for every part of this. So this level takes O of N time complexity to construct this level. So basically the number of levels we have is log N for each level. We're doing big O of N time complexity. So the overall time complexity becomes log N times N. Or in other words, we could write it as N log N time complexity where this is being multiplied by that. So overall, the big O time complexity of merge sort is N log N. Now, the memory complexity is going to be big O of N because at any point, like for this point, we're going to have to create two temporary arrays, which are these ones to build the original array. So that's going to have extra memory, which is roughly big O of N, which is the size of the original input array. So now the last question to answer is merge sort a stable sorting algorithm. Does it preserve the order of elements where there's a tie? Like when we sort this array, will this seven come before this seven? Well, we can definitely code it in such a way that it does. So first, we'll merge these two together. There's only one way to merge them together. The three, of course, is going to go before the seven. It's smaller. It has to do that. And this value, there's only one seven. So that's the only way we can have that. And now as we build our new output, we're going to have two pointers, one pointer here and one pointer here. This one is smaller, so we have no choice but to put the three over here. Next, we're going to shift this pointer to go at the next position. Now, to make sure that this is stable, we have to put this seven before this seven, because now there's a tie. How are we going to code that up? We're going to say as long as the element from the left array is less than or equal to the value in the right array, then this value is going to go in the next spot. So it matters how we handle the equality case. That's the edge case. If this one is smaller, it's going to go first. If this one is smaller, it's going to go first. But if they're both equal, then we're going to have the left element go because that makes sure that this is stable. Because if the element showed up in the left half of the array, that must mean it came in the original order. It came before the element in the right half of the array. So to add to our list, MergeSort has a time complexity, a worst case time complexity of n log n. And it's also a stable sorting algorithm. So MergeSort is in most cases preferred over insertion sort. That's why this is one of the most common sorting algorithms used. But you might be wondering, is n log n really that much more efficient than n? And the answer is yes. We know that the value n grows linearly and the formula 2 to the power of n grows very quickly. And the comparison between these two is the same comparison between n and log n. This grows so much more slowly than n. Think about it like this. If we had a value like eight and we wanted to get it to be down to one and we were decrementing it, we would go like seven, six and then keep doing that until we got down to one, that's pretty much big O of n. It's linear, but when you have something like log n, we start at eight instead of decrementing, I'm going to divide it by two. I'm going to go way fast. We're going to hit four and then we're going to divide it by two again. We're going to hit two and then we're going to hit one. This is a small example, but this is equivalent to log n. But you can imagine for really, really big numbers, it's going to be a lot faster to take a big number and keep dividing it by two to get it to one rather than taking a big number and then subtracting one, which would be linear. So log n is very, very efficient compared to n. Quicksor is another common sorting algorithm. And it's actually very, very similar to merge sort. The idea is that instead of splitting the array into two equal halves and then sorting those halves instead, we're going to pick a random value. And for convenience, we usually pick the right most value. And this is called the pivot value. So the pivot value is special because what we're going to do is we're going to iterate through every single value in the input array except for the pivot value. So basically every value before the pivot value. And we're going to compare that value to the pivot and every value that's less than or equal to the pivot value is going to be in the left partition of the array. So what we're going to do is take the input and partition it into two pieces, a left and right piece where every value that's less than the pivot, less than or equal to the pivot, is going to go in the left half and every value that's greater than the pivot is going to go in the right side. And performing this partition is actually pretty simple in terms of code. And we can actually perform the partition in place. That means we don't need to allocate any extra memory to do the partition. We can do it with just a single array. What we're going to do is take the right most value. That's going to be called our pivot. We're going to have a pointer that's going to start at the beginning of the array. And the idea is if we took every value that's less than or equal to the three and then placed them in this leftmost area, if every value in the input array that's less than or equal to three was placed over here, then by definition, all the values that are greater than three would take up the remaining spots. As long as we swap them appropriately, that's going to be the case. So all we have to worry about is taking the values less than or equal to this and then filling them starting at the left side. If we do that correctly, then the less than or equal to values will be here and the greater values will be here. So let's start doing that. So we're actually going to have two pointers. One pointer is just going to help us iterate through here. And then the second pointer is going to tell us where we should insert the next value that is less than or equal to three. So first we get to six, six is not less than or equal to three. So in this case, we don't do anything. We take our pointer over here and then shift it to the right by one. This pointer stays here because when we do find a value less than or equal to three, this is the first spot we're going to put it. So now we find a two, two is less than or equal to three. So we swap two with whatever happens to be in this position. So we can swap these two values, six goes here and then two goes here. Now this pointer that's over here is going to be shifted over here. Now, this is the next spot that we're going to insert the value that's less than or equal to three. So next we can take this pointer and then increment it one more time. So now we're at four is four less than or equal to three. It's not so we don't do anything with it. We increment our pointer one more time. We get to one one is less than or equal to three. So that means this one is going to be placed where this pointer happens to be. So we'll be swapping these two, placing the one over here and placing the six over here. And then this pointer will finally reach the pivot index. And we don't really need to do anything. We basically ignore that. But at this point, our array looks something like this. Two, one, four, six, three. We wanted to partition the array such that every value less than or equal to this was on the left side, every value greater than this was on the right side. But where should we actually put this pivot itself to satisfy that? Well, this is where our pointer ended. That means our pointer is here. That means every value to the left of that is less than or equal to three. So this is a good position to put our pivot at. So that's exactly what we're going to do with quick sort. We perform one last swap between where our left pointer is at and our pivot value. So we end with a three over here and a four in this position. So to make it more clean, after doing our partition, we have a two, a one and a three over here and we have a six and a four on the right partition. Now, notice how the left side is not sorted and the right side isn't sorted. Just because we partitioned them does not mean they're sorted. But what is true is every value on the left is less than every value on the right. Every value on the right is greater than every value on the left. Now, this is where the recursive step comes in. Now, let's run quick sort on the left side and run quick sort on the right side. Now, before we recursively run quick sort here and here, one thing to notice about the three is that it's already in sorted order. Everything to the left of it is less than or equal to it. And everything to the right of it is greater than or equal to it. So this three doesn't actually need to be part of our equation anymore. We can just ignore this. So it does exist, but we're not focusing on it. When we run quick sort on this sub problem, let's just focus on these two values. This is already exactly where it needs to be. And that's always going to be true of the pivot value. So now we're going to choose the right most element, which is going to be our pivot. So in this case, one is our pivot. We're going to start at the beginning of the array. We're going to compare two to the pivot value is two less than or equal to one. It's not so we don't do anything. And then we would take our pointer increment to be here. It's at the pivot so we don't do anything. That's when we stop. And the last thing we do before we split the array is we take the pivot and swap it with wherever our left pointer would have been. Remember, our left pointer starts here. And since we didn't end up swapping anything here, our left pointer would stay here. So what we're going to do is take one and two and then swap them. Because we know our pivot should go at the beginning. One should go at the beginning. Two should be here. And so this is the index that our pivot went to. And I didn't mention this earlier, but when we take the array and then split it into two pieces, we do it based on where the pivot value was inserted. So the pivot value three was inserted right into the middle. That's why we took the first three values and then put them over here, even though we didn't actually include the last value. And then we took all values to the right of that pivot and then, you know, ran quicksort on them over here. But so now that our pivot was over here, we're going to take the one and it will go on the right side and then all the remaining values in this case, two are going to go here. And that's essentially the base case anyway. So when we run quicksort on this and this, we're not going to do anything. Of course, an individual element is already sorted. And remember for quicksort, we're not allocating any extra memory. These swaps that we're doing are happening in place. That's the advantage of quicksort over a merge sort. We don't actually have to allocate extra arrays. Now running quicksort on these two elements, this is going to be our pivot. This is where our pointer is going to start. And this is also where our left pointer is going to be the pointer that tells us where to insert the next element that