Wednesday, November 5, 2008

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.

No comments: