So, it's a nontrivial and, and actual 
very important example. 
Let's take a look at the analysis of 
mergesort, which is the prototype for the 
study of divide-and-conquer algorithms. 
as a warm up I'm going to talk first 
about binary search which is everybody's 
first divide-and-conquer algorithm. 
and that's where we have a sorted array 
and we look to see if a particular value 
is in the array by looking at the middle. 
If the value we're looking for is less 
than the item at the middle go left, 
if it's greater go right. 
and in either case, divide the size of 
the array about in two. 
that's the code for a binary search and 
you can find it in the Algorithms book or 
in the Algorithms book site and its 
behavior is described by that recurrence. 
The number of compares in the worst case 
to find to discover that an items missing 
from an array of size N is going to be 
the, the size of the subarray that you're 
looking is going to be floor of N over 2. 
So, that's the you take N over 2 is the 
biggest integer less than that. 
if its array is size is of odd size, then 
that'll be an exact equation. 
If it's an even size, you go down one. 
and so, just check that for yourself that 
that is the number of compares in the 
worst case. 
And so now we have this mathematical 
model and that's what we want to study. 
Now usually we're trying to get an 
approximate solution or just an idea of 
about how many compares were taken. 
and the easy case for binary search is if 
the file size is exactly a power of 2, 
then divides in half then the part of the 
array that you're looking is also a power 
of 2 so, it becomes a reccurence to 
telescopes. So we'll take a sub n = B of 
2 to the n if we start with the power of 
2, and then we just have a simple 
reccurence telescopes, that's just the 
substituting B of 2 to the n. 
and then, that reccurence is the one that 
we looked at, just telescopes to a sub n 
= n, and each time we throw out a 1 for n 
times. And that means that that little n 
is log base 2 of big N by definition. 
so, the number of compares taken by 
binary search in worst case is log base 2 
of big N when n is a power of 2. 
and again, I can check that just by 
plugging into the recurrence log base 2 
of n. 
so now, but what about the general case 
when n is not necessarily a power of 2. 
Well, it turns out to be an easy way to 
study that case and that's to develop a 
correspondence with binary numbers. 
So lets define a b B sub N to be the 
number of bits in the binary 
representation of n. 
so so in this example, N is 107 and it's 
got seven bits in its binary 
representation. 
so you can check pretty easily that what 
you can do is just remove the rightmost 
bit. 
If you remove the rightmost bit you get 
floor of N over 2 and then you removed 
one bit. So what that means is, the 
number of bits in the binary 
representation of n is, for of if the 
number of bits in binary representation 
of for n over 2 plus the one bit, 
that's the same recurrence as binary 
search. 
Maybe it's a little bit easier to think 
about counting the number of bits of the 
binary representation of N than it is 
thinking about the binary search 
algorithm and so, that's an easy model. 
and then, it's pretty straightforward to 
prove that the number, that number, the 
number of bits in the binary 
representation of N is the floor of log 
base 2 of N plus 1. 
and it's worthwhile this table and these 
formulas are here for you to check that 
map for yourself to be sure that you 
understand how that might be the case. 
it's actually pretty simple calculation 
just the the leading digit of log base 2 
of N changes at the powers of two. 
and if you just ignore the rest of it, 
then you get floor of log base 2 of N and 
then we're adding 1 to that. 
And this is this map in that table is for 
you to check and prove to yourself that 
this is true. 
So we had an algorithm binary search and 
we had an idea number of bits in the 
binary representation of the numbers and 
these two are matched up through the 
recurrence. 
and that's a warm up because now we're 
going to do the same thing for mergesort. 
So mergesort everybody learned and I 
talked about it in the earlier lecture. 
divide the two array, the array into two 
halves, sort the two halves, and then 
merge to put them back together. 
for simplicity, we'll assume that the 
merge implementation always uses and 
compares, 
and then, if you do that you get this 
recurrence for the number of compares for 
the sort. 
And this kind of recurrence is more 
complicated than the ones that we've 
looked at, because of the appearance of 
the floor and ceiling functions over in 
the right-hand side. 
they're not immediately easy to deal with 
and they result in some interesting 
effects if we're trying to come up with a 
formula for the answer. 
What's the value of CN? 
we can go ahead and 
do our computation but let's first talk 
about the easy case which we already did. 
it's the same as for binary search, that 
is if N is a power of two, then the 
floors and ceilings go away floor of N 
over 2 ceiling of N over 2 are both equal 
to N over 2 or so if you do the same kind 
of thing where a sub n equals C sub N 
C sub 2 to the N. Now we get this 
recurrence here and that's one of the 
first ones we solved with the telescoping 
sum. 
The summation factor is 2 to the n 
divided by 2 to the n and then we get the 
result n 2 to the n in terms of the 
original it means that C sub cap n equals 
n log cap n when n is a power of two. 
but what if n is not a power of two? 
so that's the next question to address. 
so like there's a natural question that 
arises. 
So for quicksort, 
we did the number of compares and we got 
a very precise analysis that we can check 
against the performance of the algorithm. 
and it was asymptotically equal to 2N 
natural log n minus this constant times 
n. 
So one natural question is we want to get 
a more accurate estimate and n log n for 
mergesort is the number of compares for 
mergesort proportional to n log n plus 
alpha n for some constant alpha. 
and then we'd want to find out what alpha 
is in order to get the job done. 
and the answer to that is no. 
actually, there's no constant. 
and that's important to 
first of all, it invalidates the 
hypothesis like that and it's going to 
get in our way of us trying to 
[COUGH] approximate, accurately 
approximate the performance of mergesort. 
And it's a prototype of what can happen 
in many, many computer algorithms that 
have the same kind of characteristic. 
so 
how do I know that? 
Well here is a demonstration of what goes 
on and this is really why I wanted to 
spend the time at the beginning to 
motivate you to do go ahead and do plots. 
this is simply using the same structure 
that we use for Fibonacci and quicksort 
to go ahead and compute values of the 
mergesort recurrence. 
And then the second for loop is just 
going through and scaling it's trying to 
determine if there's this alpha value and 
so just divide by [COUGH] subtract off 
the N log N which is the leading term and 
then it actually adds N because to make 
the scale good and this is the plot that 
you get absolutely not a constant. 
it's it's something that grows in a 
strange oscillatory factor. 
And so, computing the values and actually 
plotting the values if you just plot the 
values without scaling like that, you 
might not notice this. 
it's actually kind of small initially, 
but it's important because it means 
you're not going to be able to prove that 
there's a constant or find a value of a 
constant. 
so plotting the values are very, very 
helpful and if we want to characterize 
mathematically the performance of 
mergesort, whatever result that we have, 
whatever mathematical formula that we 
have is going to have to be able to do 
this. 
This is a fundamental example. 
It's a relatively simple example. 
It comes up over and over and over again. 
And really this kind of oscillation is 
something that is intrinsic in the 
analysis of algorithms because of the 
idea that we need to go down to the 
discrete and that means that we get stuck 
in this kind of oscillations all the 
time. 
so but I do want to talk about doing 
mergesort specifically in the general 
case because it's so important. 
so and there's a little trick involved to 
simplify it a little bit that again I'm 
not going to complete motivate, but 
you'll, you'll see what I mean. 
So if we right down the same formula for 
N1. 
+ 1 then we're going to have to do some 
math with floors and ceilings. 
so floor of (N1)/2 + 1) / 2 is the 
ceiling of (N / 2) and ceiling of (N1)/2 
+ 1) is the floor of (N / 2) + 1. 
that's just you can do a little math to 
convince yourself with 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 the telescopes. 
so a 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 the difference to be 
D sub N and then that's going to be then 
the equation for D sub N. 
but the, that equation is a familiar one, 
that's the binary search equation. 
it has a different initial value, so the 
solution is D sub N equals floor of log 
base N plus 2. 
and then telescoping that one, so that's 
a C, that C sub N plus 1 minus C sub N is 
equal to that and then, so C sub N plus 1 
equals CN plus that. 
So that immediately telescopes to give 
the sum and so now, but 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. 
here's a commonatorial to prove the same 
thing. 
So, if S sub N is the number of bits in 
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 is carve off the rightmost 
bit. 
if you carve off the rightmost bit, 
then taking every other number, you get S 
of floor of N over 2. 
so it's just counting one, two, three up 
to floor of N over 2. 
and then, the [COUGH] alternate bits are 
S of ceiling of N over 2 and then the 
rightmost 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 mergesort 
satisfies. 
so that's a proof. 
So number compares taken by mergesort, is 
n minus 1 plus the number of bits in the 
binary representation of all the numbers 
less than N. 
When we think about it, that, that number 
of bits in the binary representation of 
all the numbers less than N. That's going 
to have some kind of oscillation because 
when you come to powers of two things are 
going to change. 
So this is just another way of looking at 
the number of bits in all the numbers 
less than N. 
so in one dimension, you've got N and the 
width, you have floor of log N plus 1. 
so the bits are all in a big N by floor 
of log N plus 1 box. 
But then what you can do is so, so that's 
pretty good thing, but, we don't have in 
the actual numbers, we don't have those 
leading os. 
But the leading 0s have a very simple 
pattern, it's one plus two plus four plus 
eight. 
and that's represented by that sum and 
that sum's just a geometric sum, 
so that gives the solution. 
Number of bits in all the numbers less 
than N without the leading 0s is you just 
take the square as if there's leading os 
and subtract off the leading os. 
And that, now that's an explicit 
solution, 
the number of compares taken by the 
mergesort. 
so it's that plus N minus one and that's 
again we started with an algorithm and 
then we had an idea which is the binary 
representation of all the numbers. 
And we show that the number of compares 
taken by the algorithm is equal to the 
number of bits, the binary represent, 
representational numbers less than N. 
and then we have an alternate way to 
count the number of bits numbers less 
than N and that gives us a complete 
solution. 
so, so, that's a fine formula for the 
number of compares and used by mergesort. 
and, we can, that's a relatively simple 
formula that we can use to compute the 
value. 
so that's just a summary of what we've 
done so far, 
but what about that oscillating term? 
well there's another way to deal with the 
floor of log N. 
if you write floor of log N, that's equal 
to log N itself minus the fractional 
part. 
that's what the braces do. 
If you substitute this formula into this 
solution for the number of compares by 
mergesort you can split it off into three 
functions. 
and that's again just algebra from this 
for the coefficient of N. 
I'm sorry the two functions the 
coefficient of N is one minus [COUGH] the 
fractional part of log N. 
and then the other thing that you have is 
the 2, 2 minus log N and those things are 
plotted, they look kind of antisymmetric 
but actually, it doesn't cancel out 
what's left is that little oscillating 
function. 
and if you multiply that by N, you get 
the exact function that we plotted by 
floor before. 
So you can check this math and if this is 
also described in the book. 
but it's just an indication of the kind 
of challenges that we're going to face 
when trying to analyze algorithms. 
we're it looks like things are going 
fine, but we might be stuck with an 
oscillation where things are just 
complicated, because we're working on the 
one hand with wanting to work with 
familiar functions like log N. 
and on the other hand, needing to work 
with functions that are forced to be 
integer value like the 
[COUGH] floor of log N or largest 
interger less than log N. 
that's the analysis of mergesort.