Okay, so to prove this lemma, to prove the upper bound on the running

time of the merge sort algorithm, first know that to merge two parts

of size n over 2 of our initial array, takes the linear time.

Namely, big O of n, because while the left part has size n over 2,

the right part has size n over 2.

And for merging, we basically just combo these parts from left to right.

So it takes just a linear amount of work to do this.

Which, in turn means, that if we denote by T of n the running time of our merge sort

algorithm, then it satisfies the following recurrence.

T(n) is at most 2T(n / 2) + big O(n).

Here 2T(n / 2) could response to two recursive calls.

So we denote it by T(n), the running time of our algorithm on input of size n.

So when we sort two sequences of size n / 2,

we spend time twice T(n / 2).

So the big O of n term corresponds to what we do before we make recursive calls and

what we do after recursive calls.

So what we do before is just split the input array into two halves.

What we do after is merging the results of two arrays into one array of size n.

So it is not difficult to see that all of this can be done in linear time.

So we get this recurrence, and on the next slide,

we're going to show that this recurrence implies that the running

time of our algorithm is bounded from above by n log n.

To estimate the running time of this algorithm,

let's consider its recursion tree.

Namely, at the top of this tree, we have one array of size n.

So for this array of size n, we make two recursive calls for

arrays of size n over 2.

Each of these arrays of size n over 2 in turn is split into two

arrays of size n over 4.

So we get four arrays of size of n over 4 and so on.

So in this tree, we have log n levels.

Now let's estimate the work done at each of the levels of these three separately,

namely, once again, to solve a problem of size n.

To sort an array of size n, we first prepare to make recursive calls.

In this case, we just split the array into two halves of size n over 2.

Then we do make recursive calls, and then we need to combine the results.

So all the work now inside recursive calls will be accounted for

on the lower levels of this tree.

So now what we are going to do is to account for

only the work done before the recursive calls and

after the recursive calls at each separate level.

And we know already that it takes linear time to do this.

I mean, if we have an array of size n,

it takes linear time to split it into two halves.

And then it takes linear time to combine the results of

recursive calls into one array.

So let's just denote this time by cn,

I mean let's denote the hidden constant inside big O by c.

Then what we can say is that on the top level we spend time cn.

Then on the next level, for each subarray,

we spend time c times n over 2, because the size of array is n over 2.

However, we have 2 arrays, so the total work that we do at this level is 2

multiplied by c, multiplied by n over 2, which is again just cn.

On the next level, we spend time 4 because we have 4 arrays multiplied by c,

multiplied by n over 4, because the size of the array is now n over 4.

This is a cn again, and so on.

So we have log n levels.

At each level, we do roughly cn operations.

So the total number of operations in our algorithm is cn log n,

which proves our lemma.

So again, what we've just proved is that the running time of

the merge sort algorithm is big O of n log n.

So in the next video, we will show that actually no algorithm,

no comparison based algorithms, to be completely formal, can sort a given

sequence of n elements asymptotically faster than in n log n time.

Which actually means that the merge sort algorithm is asymptotically optimal.