Q1. (a) Suppose that a linear/sequential search is made through a disordered list L, of length n, for an item X, where X is guaranteed to occur exactly once in the list. How many comparisons are made i. in the best case scenario? ii. in the worst case scenario? iii in the average case scenario? From this, write down the average case computational complexity of linear/sequential search 10 marks (b) Write down the intermediate words that are constructed after each iteration when the letters in the word "munich" are alphabetically ordered using i. insertion sort 11. merge sort [10 marks c) Calculate the computational complexity of the merge sort algorithm in the worst case 13 marks scenario