‫So now we're going to look at the big oh of merge sort.
‫So I'm going to bring up an array and we're going to start with space complexity.
‫In the first three soaring algorithms that we did, the array was sorted in place.
‫That is to say, we didn't need to create any new data or take up any new space in memory.
‫We just had the original array.
‫But with merge sort, we need to make new arrays.
‫And of course, these are broken in half and these are broken in half.
‫But this takes up as much space in memory as the original array.
‫And that means merge sort four space complexity is o of n.
‫So now let's look at time complexity.
‫The time complexity for merge sort is going to be o of n times log n plus n.
‫So if you'll recall from the big o section, this portion here is what we call a non dominant and we
‫drop non dominance and we're left with o of n times.
‫Log in.
‫So for now, I'm going to bring this back.
‫And this plus n portion is what we're going to do first where we're splitting the arrays in half.
‫So let's count the number of times that we do this.
‫It is one, two, three, four, five, six, seven.
‫So we did this seven times and N is eight.
‫So the number of splits is approximately N and as we discussed previously, this is a non dominant and
‫will be dropped from our equation.
‫So the o of n times log in portion happens when we put everything back together.
‫So N in this case is eight.
‫So we're going to touch all eight of these items, log in times.
‫So now let's walk through this.
‫When we combine these two items, think about the merge function.
‫The wild loops have to touch every value.
‫So it touches both of these and both of these and so on down the line.
‫In order to get to here, we had to touch all in items.
‫And the same is true when we combine these two, we have to touch all four of these and all four of
‫these.
‫Now, once again, we have touched all in items.
‫And then finally, to combine these two, we're having to do the same thing.
‫So let's break this down again like this.
‫So to get to here, we had to touch all in items and that we did it again and then we did it again.
‫We touched all in items three times and if you'll recall from the big O, section four O of log in,
‫log sub two of eight is three.
‫We touched all eight items three times, so the big o of this is o of n times.
‫Log in.
‫We touched in items, log in times.
‫So let's drop these numbers out and take a look at this on the graph.
‫So the big thing we're comparing o of n times log into is o of n squared.
‫So the previous three scoring algorithms were all o of n squared.
‫So in o of n times, log in time complexity is going to be much more efficient and that is merge sort
‫big o.