week 6 - complexity of merge sort master theorem

This week we had a shorter lecture due to Thanksgiving. The proof of mergeSort looks simple. Again..it's Danny who is doing it. But after reading it over and over again, it makes more sense now. We also did the Master Theorem, a kind of strategy that works somewhat like the mergeSort. We divide a problem into smaller components then combine solutions. Since the solutions are now split up into smaller parts, it should be easier to solve.

But the question is, how to apply the general theorem? on slide 9 there T(n) is equal to 3 different formulas depending if its value relative to b^l.

Now for PS3, after reading the hint for PS3, it was a little easier to write out a proof. Just kept unwinding and unwinding. It's just a sum of 3^n, n starts at 0. I shall use that as a starting point for my proof then. Another PS done. 3 more PS and many many more tests to go.