(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

(ii) the input is already sorted in descending order

(iii) the input contains n copies of the same number

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

(ii) 50, 25, 26, 27, 40, 44