WEEK #6

Time-complexity of search/sort algorithms were revisited this week with an analysis of the merge-sort algorithm. However, in this case we had to deal with powers of 2 within the derived time-complexity function which needed a different process in order to prove that the function will work for any natural number n. We had to first start by proving for numbers that are powers of two and then prove that the function is monotonic which will result in a proof that the function holds for numbers between powers of 2. This method is very flexible since it can be used for functions that contain powers of any number which is very common in divide-and-conquer algorithms.