1 00:00:03,680 --> 00:00:08,460 So, it's a nontrivial and, and actual very important example. 2 00:00:08,460 --> 00:00:13,137 Let's take a look at the analysis of mergesort, which is the prototype for the 3 00:00:13,137 --> 00:00:17,874 study of divide-and-conquer algorithms. as a warm up I'm going to talk first 4 00:00:17,874 --> 00:00:22,791 about binary search which is everybody's first divide-and-conquer algorithm. 5 00:00:22,791 --> 00:00:27,828 and that's where we have a sorted array and we look to see if a particular value 6 00:00:27,828 --> 00:00:32,625 is in the array by looking at the middle. If the value we're looking for is less 7 00:00:32,625 --> 00:00:36,283 than the item at the middle go left, if it's greater go right. 8 00:00:36,283 --> 00:00:40,121 and in either case, divide the size of the array about in two. 9 00:00:40,121 --> 00:00:46,333 that's the code for a binary search and you can find it in the Algorithms book or 10 00:00:46,333 --> 00:00:52,895 in the Algorithms book site and its behavior is described by that recurrence. 11 00:00:52,895 --> 00:01:00,009 The number of compares in the worst case to find to discover that an items missing 12 00:01:00,009 --> 00:01:05,954 from an array of size N is going to be the, the size of the subarray that you're 13 00:01:05,954 --> 00:01:12,238 looking is going to be floor of N over 2. So, that's the you take N over 2 is the 14 00:01:12,238 --> 00:01:17,486 biggest integer less than that. if its array is size is of odd size, then 15 00:01:17,486 --> 00:01:22,044 that'll be an exact equation. If it's an even size, you go down one. 16 00:01:22,044 --> 00:01:27,707 and so, just check that for yourself that that is the number of compares in the 17 00:01:27,707 --> 00:01:31,022 worst case. And so now we have this mathematical 18 00:01:31,022 --> 00:01:37,618 model and that's what we want to study. Now usually we're trying to get an 19 00:01:37,618 --> 00:01:44,502 approximate solution or just an idea of about how many compares were taken. 20 00:01:44,502 --> 00:01:52,305 and the easy case for binary search is if the file size is exactly a power of 2, 21 00:01:52,305 --> 00:01:59,148 then divides in half then the part of the array that you're looking is also a power 22 00:01:59,148 --> 00:02:04,849 of 2 so, it becomes a reccurence to telescopes. So we'll take a sub n = B of 23 00:02:04,849 --> 00:02:10,354 2 to the n if we start with the power of 2, and then we just have a simple 24 00:02:10,354 --> 00:02:15,203 reccurence telescopes, that's just the substituting B of 2 to the n. 25 00:02:15,203 --> 00:02:20,708 and then, that reccurence is the one that we looked at, just telescopes to a sub n 26 00:02:20,708 --> 00:02:27,065 = n, and each time we throw out a 1 for n times. And that means that that little n 27 00:02:27,065 --> 00:02:32,955 is log base 2 of big N by definition. so, the number of compares taken by 28 00:02:32,955 --> 00:02:38,725 binary search in worst case is log base 2 of big N when n is a power of 2. 29 00:02:38,725 --> 00:02:45,510 and again, I can check that just by plugging into the recurrence log base 2 30 00:02:45,510 --> 00:02:49,881 of n. so now, but what about the general case 31 00:02:49,881 --> 00:02:57,226 when n is not necessarily a power of 2. Well, it turns out to be an easy way to 32 00:02:57,226 --> 00:03:03,597 study that case and that's to develop a correspondence with binary numbers. 33 00:03:03,597 --> 00:03:09,260 So lets define a b B sub N to be the number of bits in the binary 34 00:03:09,260 --> 00:03:16,548 representation of n. so so in this example, N is 107 and it's 35 00:03:16,548 --> 00:03:19,427 got seven bits in its binary representation. 36 00:03:19,427 --> 00:03:28,962 so you can check pretty easily that what you can do is just remove the rightmost 37 00:03:28,962 --> 00:03:33,010 bit. If you remove the rightmost bit you get 38 00:03:33,010 --> 00:03:38,505 floor of N over 2 and then you removed one bit. So what that means is, the 39 00:03:38,505 --> 00:03:43,205 number of bits in the binary representation of n is, for of if the 40 00:03:43,205 --> 00:03:48,427 number of bits in binary representation of for n over 2 plus the one bit, 41 00:03:48,427 --> 00:03:51,300 that's the same recurrence as binary search. 42 00:03:51,300 --> 00:03:56,814 Maybe it's a little bit easier to think about counting the number of bits of the 43 00:03:56,814 --> 00:04:01,853 binary representation of N than it is thinking about the binary search 44 00:04:01,853 --> 00:04:08,048 algorithm and so, that's an easy model. and then, it's pretty straightforward to 45 00:04:08,048 --> 00:04:12,610 prove that the number, that number, the number of bits in the binary 46 00:04:12,610 --> 00:04:16,900 representation of N is the floor of log base 2 of N plus 1. 47 00:04:16,900 --> 00:04:25,167 and it's worthwhile this table and these formulas are here for you to check that 48 00:04:25,167 --> 00:04:32,617 map for yourself to be sure that you understand how that might be the case. 49 00:04:32,617 --> 00:04:40,108 it's actually pretty simple calculation just the the leading digit of log base 2 50 00:04:40,108 --> 00:04:44,978 of N changes at the powers of two. and if you just ignore the rest of it, 51 00:04:44,978 --> 00:04:49,783 then you get floor of log base 2 of N and then we're adding 1 to that. 52 00:04:49,783 --> 00:04:55,887 And this is this map in that table is for you to check and prove to yourself that 53 00:04:55,887 --> 00:04:59,393 this is true. So we had an algorithm binary search and 54 00:04:59,393 --> 00:05:04,848 we had an idea number of bits in the binary representation of the numbers and 55 00:05:04,848 --> 00:05:08,160 these two are matched up through the recurrence. 56 00:05:08,160 --> 00:05:13,600 and that's a warm up because now we're going to do the same thing for mergesort. 57 00:05:13,600 --> 00:05:19,018 So mergesort everybody learned and I talked about it in the earlier lecture. 58 00:05:19,018 --> 00:05:24,169 divide the two array, the array into two halves, sort the two halves, and then 59 00:05:24,169 --> 00:05:28,985 merge to put them back together. for simplicity, we'll assume that the 60 00:05:28,985 --> 00:05:32,062 merge implementation always uses and compares, 61 00:05:32,062 --> 00:05:37,547 and then, if you do that you get this recurrence for the number of compares for 62 00:05:37,547 --> 00:05:40,643 the sort. And this kind of recurrence is more 63 00:05:40,643 --> 00:05:45,907 complicated than the ones that we've looked at, because of the appearance of 64 00:05:45,907 --> 00:05:50,062 the floor and ceiling functions over in the right-hand side. 65 00:05:50,062 --> 00:05:56,296 they're not immediately easy to deal with and they result in some interesting 66 00:05:56,296 --> 00:06:00,798 effects if we're trying to come up with a formula for the answer. 67 00:06:00,798 --> 00:06:04,400 What's the value of CN? we can go ahead and 68 00:06:04,400 --> 00:06:10,715 do our computation but let's first talk about the easy case which we already did. 69 00:06:10,715 --> 00:06:16,595 it's the same as for binary search, that is if N is a power of two, then the 70 00:06:16,595 --> 00:06:22,983 floors and ceilings go away floor of N over 2 ceiling of N over 2 are both equal 71 00:06:22,983 --> 00:06:29,590 to N over 2 or so if you do the same kind of thing where a sub n equals C sub N 72 00:06:29,590 --> 00:06:35,110 C sub 2 to the N. Now we get this recurrence here and that's one of the 73 00:06:35,110 --> 00:06:39,042 first ones we solved with the telescoping sum. 74 00:06:39,042 --> 00:06:45,319 The summation factor is 2 to the n divided by 2 to the n and then we get the 75 00:06:45,319 --> 00:06:52,049 result n 2 to the n in terms of the original it means that C sub cap n equals 76 00:06:52,049 --> 00:06:57,797 n log cap n when n is a power of two. but what if n is not a power of two? 77 00:06:57,797 --> 00:07:04,178 so that's the next question to address. so like there's a natural question that 78 00:07:04,178 --> 00:07:05,910 arises. So for quicksort, 79 00:07:05,910 --> 00:07:11,884 we did the number of compares and we got a very precise analysis that we can check 80 00:07:11,884 --> 00:07:18,232 against the performance of the algorithm. and it was asymptotically equal to 2N 81 00:07:18,232 --> 00:07:21,368 natural log n minus this constant times n. 82 00:07:21,368 --> 00:07:28,243 So one natural question is we want to get a more accurate estimate and n log n for 83 00:07:28,243 --> 00:07:33,778 mergesort is the number of compares for mergesort proportional to n log n plus 84 00:07:33,778 --> 00:07:39,388 alpha n for some constant alpha. and then we'd want to find out what alpha 85 00:07:39,388 --> 00:07:44,698 is in order to get the job done. and the answer to that is no. 86 00:07:44,698 --> 00:07:49,560 actually, there's no constant. and that's important to 87 00:07:49,560 --> 00:07:54,646 first of all, it invalidates the hypothesis like that and it's going to 88 00:07:54,646 --> 00:07:59,139 get in our way of us trying to [COUGH] approximate, accurately 89 00:07:59,139 --> 00:08:04,848 approximate the performance of mergesort. And it's a prototype of what can happen 90 00:08:04,848 --> 00:08:10,140 in many, many computer algorithms that have the same kind of characteristic. 91 00:08:10,140 --> 00:08:13,856 so how do I know that? 92 00:08:13,856 --> 00:08:21,061 Well here is a demonstration of what goes on and this is really why I wanted to 93 00:08:21,061 --> 00:08:27,364 spend the time at the beginning to motivate you to do go ahead and do plots. 94 00:08:27,364 --> 00:08:34,943 this is simply using the same structure that we use for Fibonacci and quicksort 95 00:08:34,943 --> 00:08:39,730 to go ahead and compute values of the mergesort recurrence. 96 00:08:39,730 --> 00:08:47,275 And then the second for loop is just going through and scaling it's trying to 97 00:08:47,275 --> 00:08:54,981 determine if there's this alpha value and so just divide by [COUGH] subtract off 98 00:08:54,981 --> 00:09:03,462 the N log N which is the leading term and then it actually adds N because to make 99 00:09:03,462 --> 00:09:09,957 the scale good and this is the plot that you get absolutely not a constant. 100 00:09:09,957 --> 00:09:14,409 it's it's something that grows in a strange oscillatory factor. 101 00:09:14,409 --> 00:09:20,057 And so, computing the values and actually plotting the values if you just plot the 102 00:09:20,057 --> 00:09:24,177 values without scaling like that, you might not notice this. 103 00:09:24,177 --> 00:09:29,293 it's actually kind of small initially, but it's important because it means 104 00:09:29,293 --> 00:09:34,941 you're not going to be able to prove that there's a constant or find a value of a 105 00:09:34,941 --> 00:09:38,680 constant. so plotting the values are very, very 106 00:09:38,680 --> 00:09:44,018 helpful and if we want to characterize mathematically the performance of 107 00:09:44,018 --> 00:09:49,656 mergesort, whatever result that we have, whatever mathematical formula that we 108 00:09:49,656 --> 00:09:52,659 have is going to have to be able to do this. 109 00:09:52,659 --> 00:09:57,565 This is a fundamental example. It's a relatively simple example. 110 00:09:57,565 --> 00:10:04,009 It comes up over and over and over again. And really this kind of oscillation is 111 00:10:04,009 --> 00:10:09,575 something that is intrinsic in the analysis of algorithms because of the 112 00:10:09,575 --> 00:10:15,524 idea that we need to go down to the discrete and that means that we get stuck 113 00:10:15,524 --> 00:10:18,770 in this kind of oscillations all the time. 114 00:10:18,770 --> 00:10:25,677 so but I do want to talk about doing mergesort specifically in the general 115 00:10:25,677 --> 00:10:34,206 case because it's so important. so and there's a little trick involved to 116 00:10:34,206 --> 00:10:40,942 simplify it a little bit that again I'm not going to complete motivate, but 117 00:10:40,942 --> 00:10:46,971 you'll, you'll see what I mean. So if we right down the same formula for 118 00:10:46,971 --> 00:10:50,306 N1. + 1 then we're going to have to do some 119 00:10:50,306 --> 00:10:54,898 math with floors and ceilings. so floor of (N1)/2 + 1) / 2 is the 120 00:10:54,898 --> 00:10:59,661 ceiling of (N / 2) and ceiling of (N1)/2 + 1) is the floor of (N / 2) + 1. 121 00:10:59,661 --> 00:11:05,273 that's just you can do a little math to convince yourself with that. 122 00:11:05,273 --> 00:11:11,481 so that's what this table does. and then, once we have that, then we can 123 00:11:11,481 --> 00:11:17,860 subtract those two formulas and that gives us something the telescopes. 124 00:11:17,860 --> 00:11:24,575 so a little magic trickery based on the relationships between floor and ceiling 125 00:11:24,575 --> 00:11:30,287 with the plus ones and that gives us a simpler formula to work with. 126 00:11:30,287 --> 00:11:37,156 so we'll just define the difference to be D sub N and then that's going to be then 127 00:11:37,156 --> 00:11:42,405 the equation for D sub N. but the, that equation is a familiar one, 128 00:11:42,405 --> 00:11:48,222 that's the binary search equation. it has a different initial value, so the 129 00:11:48,222 --> 00:11:52,380 solution is D sub N equals floor of log base N plus 2. 130 00:11:52,380 --> 00:12:01,263 and then telescoping that one, so that's a C, that C sub N plus 1 minus C sub N is 131 00:12:01,263 --> 00:12:07,636 equal to that and then, so C sub N plus 1 equals CN plus that. 132 00:12:07,636 --> 00:12:14,929 So that immediately telescopes to give the sum and so now, but what's 133 00:12:14,929 --> 00:12:21,595 interesting about that sum is, that this thing here is the number of bits in the 134 00:12:21,595 --> 00:12:27,177 binary representation of k. so this is a proof that C sub N equals N minus 1 plus 135 00:12:27,177 --> 00:12:33,176 the number of bits in the binary representation of all the numbers less 136 00:12:33,176 --> 00:12:41,188 than N and that's a interesting fact. here's a commonatorial to prove the same 137 00:12:41,188 --> 00:12:45,033 thing. So, if S sub N is the number of bits in 138 00:12:45,033 --> 00:12:52,287 the binary representation of all the numbers less than N then what we can do 139 00:12:52,287 --> 00:12:58,230 is just over in the left is all the numbers less than 15. 140 00:12:58,230 --> 00:13:02,150 and what we do is carve off the rightmost bit. 141 00:13:02,150 --> 00:13:07,784 if you carve off the rightmost bit, then taking every other number, you get S 142 00:13:07,784 --> 00:13:12,325 of floor of N over 2. so it's just counting one, two, three up 143 00:13:12,325 --> 00:13:16,797 to floor of N over 2. and then, the [COUGH] alternate bits are 144 00:13:16,797 --> 00:13:21,269 S of ceiling of N over 2 and then the rightmost bits are N - 1. 145 00:13:21,269 --> 00:13:26,159 So, that's a combinatorial proof that the number of bits in the binary 146 00:13:26,159 --> 00:13:31,888 representation of all the numbers less than N satisfies this recurrence that's 147 00:13:31,888 --> 00:13:35,102 the same recurrence that mergesort satisfies. 148 00:13:35,102 --> 00:13:39,757 so that's a proof. So number compares taken by mergesort, is 149 00:13:39,757 --> 00:13:45,069 n minus 1 plus the number of bits in the binary representation of all the numbers 150 00:13:45,069 --> 00:13:48,753 less than N. When we think about it, that, that number 151 00:13:48,753 --> 00:13:54,561 of bits in the binary representation of all the numbers less than N. That's going 152 00:13:54,561 --> 00:14:01,502 to have some kind of oscillation because when you come to powers of two things are 153 00:14:01,502 --> 00:14:05,610 going to change. So this is just another way of looking at 154 00:14:05,610 --> 00:14:09,365 the number of bits in all the numbers less than N. 155 00:14:09,365 --> 00:14:17,316 so in one dimension, you've got N and the width, you have floor of log N plus 1. 156 00:14:17,316 --> 00:14:23,752 so the bits are all in a big N by floor of log N plus 1 box. 157 00:14:23,752 --> 00:14:30,856 But then what you can do is so, so that's pretty good thing, but, we don't have in 158 00:14:30,856 --> 00:14:34,321 the actual numbers, we don't have those leading os. 159 00:14:34,321 --> 00:14:39,683 But the leading 0s have a very simple pattern, it's one plus two plus four plus 160 00:14:39,683 --> 00:14:42,822 eight. and that's represented by that sum and 161 00:14:42,822 --> 00:14:46,680 that sum's just a geometric sum, so that gives the solution. 162 00:14:46,680 --> 00:14:51,802 Number of bits in all the numbers less than N without the leading 0s is you just 163 00:14:51,802 --> 00:14:56,531 take the square as if there's leading os and subtract off the leading os. 164 00:14:56,531 --> 00:14:58,839 And that, now that's an explicit solution, 165 00:14:58,839 --> 00:15:01,710 the number of compares taken by the mergesort. 166 00:15:01,710 --> 00:15:08,502 so it's that plus N minus one and that's again we started with an algorithm and 167 00:15:08,502 --> 00:15:13,631 then we had an idea which is the binary representation of all the numbers. 168 00:15:13,631 --> 00:15:19,523 And we show that the number of compares taken by the algorithm is equal to the 169 00:15:19,523 --> 00:15:23,890 number of bits, the binary represent, representational numbers less than N. 170 00:15:23,890 --> 00:15:29,504 and then we have an alternate way to count the number of bits numbers less 171 00:15:29,504 --> 00:15:32,970 than N and that gives us a complete solution. 172 00:15:32,970 --> 00:15:40,162 so, so, that's a fine formula for the number of compares and used by mergesort. 173 00:15:40,162 --> 00:15:47,023 and, we can, that's a relatively simple formula that we can use to compute the 174 00:15:47,023 --> 00:15:52,153 value. so that's just a summary of what we've 175 00:15:52,153 --> 00:15:57,199 done so far, but what about that oscillating term? 176 00:15:57,199 --> 00:16:04,130 well there's another way to deal with the floor of log N. 177 00:16:04,130 --> 00:16:10,894 if you write floor of log N, that's equal to log N itself minus the fractional 178 00:16:10,894 --> 00:16:14,001 part. that's what the braces do. 179 00:16:14,001 --> 00:16:22,410 If you substitute this formula into this solution for the number of compares by 180 00:16:22,410 --> 00:16:26,980 mergesort you can split it off into three functions. 181 00:16:26,980 --> 00:16:34,982 and that's again just algebra from this for the coefficient of N. 182 00:16:34,982 --> 00:16:42,570 I'm sorry the two functions the coefficient of N is one minus [COUGH] the 183 00:16:42,570 --> 00:16:49,472 fractional part of log N. and then the other thing that you have is 184 00:16:49,472 --> 00:16:56,913 the 2, 2 minus log N and those things are plotted, they look kind of antisymmetric 185 00:16:56,913 --> 00:17:02,973 but actually, it doesn't cancel out what's left is that little oscillating 186 00:17:02,973 --> 00:17:06,133 function. and if you multiply that by N, you get 187 00:17:06,133 --> 00:17:09,950 the exact function that we plotted by floor before. 188 00:17:09,950 --> 00:17:15,002 So you can check this math and if this is also described in the book. 189 00:17:15,002 --> 00:17:20,395 but it's just an indication of the kind of challenges that we're going to face 190 00:17:20,395 --> 00:17:25,447 when trying to analyze algorithms. we're it looks like things are going 191 00:17:25,447 --> 00:17:30,773 fine, but we might be stuck with an oscillation where things are just 192 00:17:30,773 --> 00:17:36,166 complicated, because we're working on the one hand with wanting to work with 193 00:17:36,166 --> 00:17:41,423 familiar functions like log N. and on the other hand, needing to work 194 00:17:41,423 --> 00:17:48,080 with functions that are forced to be integer value like the 195 00:17:48,080 --> 00:17:53,117 [COUGH] floor of log N or largest interger less than log N. 196 00:17:53,117 --> 00:17:55,880 that's the analysis of mergesort.