Problem 1 For each algorithm listed below, give a recurrence that describes its worst-case running time, and give its worst-case running time using -notation. You need not justify your answers. (a) Merge sort (b) Insertion sort (c) Merge's algorithm (d) Binary Search Problem 2 Do Quicksort on the input numbers 12,7,10,3,8,6. Illustrate the execution using a binary tree where each node is an array or subarray when calling the PARTITION procedure. The two children of a node are the subarrays immediately after partitioning their parent array. Problem 3 Consider a variation of MergeSort which divides the list of elements into two lists of size 2/5 and 3/5, recursively at each step, instead of dividing it into halves. The Merge procedure does not change. (a) Give a recurrence relation for this algorithm (b) Draw a recursion tree for the algorithm (c) Using the recursion tree, explain how the worst case upper bound is O(nlogn)