2. Questions on Sorting algorithms, Binary Search Tree, AVL Tree and Algorithm Analysis. [Total Marks = 50 marks] (a) Let us consider both Merge Sort and Insertion Sort in which we want to sort an input array of n integers in ascending order. What will be the worst case asymptotic upper bound on the running time if (i) the input is already sorted in ascending order [5 marks] (ii) the input is already sorted in descending order [5 marks] (iii) the input contains n copies of the same number [5 marks] State and justify your answer for each scenario and algorithm. (b) Suppose that we want to search for the number 47 in a binary search tree which have numbers between 1 and 99. State and justify your answer in words whether the following sequences could be the possible sequence of nodes examined. (i) 5, 2, 1, 10, 39, 34, 77, 63 [5 marks] (ii) 50, 25, 26, 27, 40, 44 [5 marks] (c) Suppose that we insert an element y into a non-empty binary search tree that does not already contain y. Then we immediately delete it from the tree. Will the tree after deletion be identical to the original one? Justify your answer with no more than 5 sentences. Draw pictures if necessary. [5 marks] (d) Consider the following algorithm to find the smallest item in a list of n distinct integers: 1. Pick an element, x, from the list at random. 2. Go through every other element in the list. If an element is less than x put it in list 1, and if it's more than x, put it in list 2. (Note: Since all elements in the list are distinct, none will equal to x.) 3. If list 1 is empty, then return x, since it's the smallest element. If list 1 is NOT empty, go back to the first step, only using list 1. In terms of n, what is the best case run-time of this algorithm? In terms of n, what is the worst case run-time of this algorithm? Justify both answers in words. [10 marks]