Week 6

This week we focused on analyzing the complexity of mergesort and did some unwinding and proof. The repeating substitution procedure is simple. In most cases, when n>some integer, according to the definition, we can easily get a formula from the right hand side. Since we want the f(n) or g(n) or whatever to decrease to f(0)/g(0)=1, the formula we eventually derive will be like a constant to the power of something plus something else. To make a conjecture, we just carefully define n, which is usually natural numbers with some restrictions. The divide-and-conquer strategy provides us a way of breaking big problems into smaller and smaller parts. Then the size will be small enought for us to directly solve. Well, at least with spliting up and solving one of the subproblems, the base cases, we can always get a few marks.