2 Shell Sort (20 points) (Learning Objectives 2 and 3) (a) (10 points) Consider the following example array, and the sequence ,2,4,2P] for Shell sort. Assume that there are n elements in the array, and 2P is the largest power of 2 that is less than (a(i) (2 points) For each of the 2P-sorting. 4-sorting, and 2-sorting. what is the time complexity in terms of n? Justify your answer. ANS: (a)ii (2 points) What is the total time complexity of performing 2P-sorting,.... 4-sorting, and 2-sorting? Justify your answer. ANS: (aiii (4 points) What is the time complexity of performing 1-sorting? What is the overall time complexity of performing Shell sort using the sequence 1,2,4,. 2? Justify your answer. ANS: (a(iv) (2 points) Provide an example where the time complexity of Shell sort is as high as that in (a)(ii) when the sequence used is 1,3,9,3*. where 34 is the largest power of 3 that is less than n ANS