What is the length of the shortest path from the root to a leaf in any decision tree of Insertion Sort algorithm, where is the size of the input array? (a) (1) (b) (logn) (c) (n) (d) (nlogn) (e) (n2) Arthur was programming Quick Sort. Then, Merlin came to Arthur, and said he could use his magic to run Partition() method in O(1). (We don't know how Merlin could do it in O(1). He used a magic.) So, instead of q=Partition(A,p,r) QuickSort(A, p, q-1) QuickSort(A, q+1,r) Arthur programmed as below: q= AskMerlinForPartition(A, p,r) QuickSort(A, p, q-1) QuickSort(A, q+1,r) where AskMerlinForPartition takes O(1) time. What would be the worst running time and the best running time of Arthur's Quick Sort Program? (a) Worst: (n2), Best: (nlogn) (b) Worst: (n), Best: (logn) (c) Worst: (nlogn), Best: (nlogn) (d) Worst: (n), Best: (n) (e) Worst: (logn), Best: (logn) What is the length of the shortest path from the root to a leaf in any decision tree of Merge Sort algorithm, where n is the size of the input array? (a) (1) (b) (logn) (c) (n) (d) (nlogn) (e) (n2) Given array [22,35,94,22,75,67,17,87,54,73], what is the resulting array after the Partition function in class was applied once? (The last element is picked as a pivot.) (a) [22,35,22,67,17,54,73,94,75,87] (b) [17,22,22,35,54,67,73,75,87,94] (c) [22,35,22,67,17,54,73,87,94,75] (d) [22,35,22,67,17,54,73,75,87,94] (e) [17,22,22,35,54,67,73,94,75,87]