Divide and Conquer is conquering me.

I'm currently studying for test 2 and I am reviewing the lecture slides and the examples in the text. I'm a little bit confuzzled about the divide and conquer example that was given in lecture regarding the time complexity of MergeSort. I think I understand why monotonicity is used here to prove that the counting method can be applied for all integers that are not of the form 2^k. In the scope of this problem it works because we are proving the inequality T(n) < Xlog_2(n). This can easily be proved for the special case and then monotonicity is used to show that for any natural number that is not of the form 2^k is less that some natural number that is and consequently satisfies the inequality as well. I'm hoping I have the right idea. It makes sense but this method can only be used when proving an inequality. I hope I have the right idea. Writing it out seems to help me make more sense of it. I should check the slides again.

A2 Graded. HOORAY? BOO?

Actually, it's a "Hooray" for my partner and I. We were both really worried about the first problem involving ternary trees. Instead of finding a formula, we developed a recursive method in python to count the number of configurations of ternary trees. Then we developed a pre-condition and post-condition for our method and proved its correctness in regard to our conditions. We got a pretty good mark for that question, so I'm happy. Hmm... we should probably show our proof to Danny. I'm sure he's interested to see how we proved our algorithm considering it took us forever and a day to come up with it in the first place.