Week VI

For the first time when I tried to solve the problem set question, I was plugging some numbers into the function which was so stupid. However, once I went over the lecture notes then I knew what was wrong with me. The hint was given! - the repeating substitution. After I kept substituting functions again and again, I faced another problem that I could not get the closed-form, had hard time to figure it out. So I visited general TA office centre to get some hint. After, I started seeing a pattern and realized that the closed-form, or simplified form is created when it meets base case from the main function.
I needed to know when it stops and then plug the base case (initial number) into the closed-form. Now,
It was not done yet. I needed to prove it in order to see whether my conjecture, the closed-form is correct or now. Luckily, I proved thoroughly with well-organized structure. I was pretty satisfied with that, hoping I get good mark on this. After finishing the problem set, I realized this is an easy question. I do not expect this level of question on the second mid-term.

This week lecture was about 'Complexity of merge sort & master theorem'. Master Theorem has somewhat relation with the merge sort : divide up a problem into subproblems of the same type, and then combine the solutions to the sub-problems The "smallest" instances of the problem can be solved directly. Right now, I am still confused about this strategy. I might go read over the textbook or some websites. But roughly, the theorem seems very standard and obvious.