Week 6 - Complexity of Merge Sort Master Theorem

I was never good with sorting in first year, especially merge sort. Now that it's being touched on again, I think I should spend more time on it this time. Merge sort is an instance of a general strategy: divide up a problem into subproblems of the same type, and then combine the solutions to the subproblems. The "smallest" instances of the problem can be solved directly. This is a useful strategy, and it sounds similiar to the principle of induction. But overall, I was quite lost during this lecture, it's time again to do some studies at home.

I also received my test back this week... very shocked by the speed of marking. I was VERY disappointed with my test result however, I thought I did pretty well. But it turns out that my careless mistakes killed me hard. I lost tons of marks on what I thought was the easiest question... This test has definitely rang a bell: be more conscientious next time! Though I think I will be asking for a remark, the almost 30% deduction was too harsh for a careless mistake.


PROBLEM SET #3

After unwinding the function, I couldn't find a pattern to make a conjecture about a closed-form for it. This question seemed very hard until my friend gave me a hint as to what the pattern is. It wasn't obvious to me at all. What if the same question comes up on the test and I don't have all that time to look for a pattern? Or what if I get totally stuck like this time? Maybe doing more practice problems will help.