This is a fundamental example,

it is a relatively simple example, comes over and over and over again.

And really this kind of isolation,

something that is intrinsic, and the analysis are over this

because of the idea that we need to go down to the discreet.

And that means that we get stuck in this kind of oscillation all the time.

So but I do want to talk about undoing mergesort

specifically in the general case because it's so important.

So and there is a little trick involved to simplify it a little bit.

That again I'm not going to completely motivate.

But you'll see what I mean.

So if we write down the same formula for n plus 1.

Then we are going to have to do some math with floors and ceilings.

So floor of n plus 1 over 2 is the ceiling of n over 2.

And ceiling of n plus 1 over 2 is the.

Floor of n over 2 + 1.

That's just, you can do a little math to convince yourself of that.

So that's what this table does.

And then once we have that, then we can subtract those two formulas.

And that gives us something that telescopes, so

little magic trickery based on the relationships between floor and

ceiling with the plus ones, and that gives us a simpler formula to work with.

So we'll just define that difference to be D sub N,

and that's going to then be the equation for

D sub N But, that equation is a familiar one.

That's the binary search equation.

It has a different initial value, so the solution is DN = floor of lgN + 2.

And then telescoping that one,

so that's CN+1- CN = that,

And then so Cn plus one equals Cn plus that so

then immediately telescopes to give this sum.

And so, now what's interesting about that sum is that this thing here is

the number of bits in the binary representation of K So

this is a proof that C sub N equals N minus 1 plus the number of

bits in the binary representation of all the numbers less than N.

And that's a interesting fact,

that here's a combinatorial way to prove the same thing.

So if s sub n is the number of bits and

the binary representation of all the numbers less than n,

then what we can do is just over in the left is all the numbers less than 15.

And what we do carve off the right most bit.

If you carve off the right most bit, then taking every other number,

you get s of over 2.

So it's just counting one, two, three up to over 2.

And then The [COUGH] alternate bits are at the ceiling of N/2,

and then the right-most bits are N-1.

So that's a combinatorial proof that the number of bits in the binary

representation of all the numbers less than N satisfies this recurrence,

that's the same recurrence that merge sort satisfies.

So that's a proof So number compares taken by merge sort is ms1 plus number

of bits in the binary representation of all the numbers less than n.

And when you think about it, that number of bits in the binary representation

of all the numbers less than n, that's going to have some kind of oscillation.