October, Week 6

This week we used the unwinding technique along with other tools to solve more problems. One of such problems was to find the time complexity of mergeSort() python function. This problem served as a good example of how different tools can be mixed together to prove something. At the lecture, Danny Heap first found T(n) with unwinding, but only for powers of 2. He then showed the monotonicity of T(n), which would allow us to make conclusions for all n \in N, and not just powers of 2. Danny Heap also introduced the "master theorem for divide-and-conquer", the principle that was used to solve T(n) of mergeSort().