For sorting problem, there are two categories of algorithms: one sorts by reducing the problem size by one at each step, and the other category of algorithms divides the problem into two smaller problems, solves each smaller problem recursively, and combines the two sorted lists. If the Insertion sort algorithm (in Section 2.1) starts with input size n, after first iteration one element (smallest or largest) is at correct location and other (n 1) elements needs sorting. We write the equation below and solve it for finding complexity of the algorithm. T(n) = kn+T(n-1), where T(n) denotes time to sort n numbers and k is a constant that is computer dependent. After solving this equation we find that the complexity of this algorithm is 0 (m2). Merge sort and Quick sort algorithms divide the list of elements into two smaller lists, and then recursively sort both smaller lists. The Merge sort algorithm divides the list of elements into two smaller lists of approximately equal sizes in constant time, recursively sort smaller lists, and then merge the two sorted lists in (kn) time. (a) Write an equation for finding complexity of the Merge sort algorithm. (b) Solve the equation to show that time complexity of the Merge sort is O(n log n)