P6 (15 points). Analyze Quicksort: Recall the Quicksort algorithm. Sup- pose we are given a set of n distinct numbers, Ag = {x1, ..., Xn}. The goal is to sort them in the increasing order. In the first step, we take Ao as the input. Pick a number uniformly at random from A0, and suppose the number is yi. Compare all the numbers in Ao with yi and split the numbers into two sets A1 and B1. Set Aj contains all the numbers less than y; set B1 contains all the numbers greater than yl. We see that the randomly chosen number y is used to partition the input set to two subsets. Let us call such randomly selected yi a partition point. Next, repeat the same procedure on set Aj and set B1 separately, using Aj and B as the input for each, as long as the input set has more than one element. Running the procedure on A leads to two sets; and running the procedure on B1 leads to two sets. We then repeat the same procedure on each of the four sets, as long as an input set contains more than one element. The process continues until all the sets have no more than one element. As an example, suppose we will sort the numbers in {5, 16, 2, 10, 13, 4, 20,8} We pick a number uniformly at random, and suppose the number is y1 = 10. After comparing all the numbers with 10, we obtain two subsets: {5, 2, 4,8} and {16, 13, 20}. We then repeat the procedure separately on each of the two sets. When repeating the procedure using {5, 2,4,8} as the input, we pick a number from {5, 2, 4,8} uniformly at random and suppose the num- 4 is picked. After the numbers in the input set {5, 2, 4,8} are compared with 4, we obtain two subsets: {2} and {5,8}. The procedure will be repeated for the set {5,8). In the end, all the sets will have no more than one element and we are done. Question: Let X be the number of comparisons made during the whole sorting process. Compute E[X] and show E[X] ~ 2n log n for large n. ber y2 = P6 (15 points). Analyze Quicksort: Recall the Quicksort algorithm. Sup- pose we are given a set of n distinct numbers, Ag = {x1, ..., Xn}. The goal is to sort them in the increasing order. In the first step, we take Ao as the input. Pick a number uniformly at random from A0, and suppose the number is yi. Compare all the numbers in Ao with yi and split the numbers into two sets A1 and B1. Set Aj contains all the numbers less than y; set B1 contains all the numbers greater than yl. We see that the randomly chosen number y is used to partition the input set to two subsets. Let us call such randomly selected yi a partition point. Next, repeat the same procedure on set Aj and set B1 separately, using Aj and B as the input for each, as long as the input set has more than one element. Running the procedure on A leads to two sets; and running the procedure on B1 leads to two sets. We then repeat the same procedure on each of the four sets, as long as an input set contains more than one element. The process continues until all the sets have no more than one element. As an example, suppose we will sort the numbers in {5, 16, 2, 10, 13, 4, 20,8} We pick a number uniformly at random, and suppose the number is y1 = 10. After comparing all the numbers with 10, we obtain two subsets: {5, 2, 4,8} and {16, 13, 20}. We then repeat the procedure separately on each of the two sets. When repeating the procedure using {5, 2,4,8} as the input, we pick a number from {5, 2, 4,8} uniformly at random and suppose the num- 4 is picked. After the numbers in the input set {5, 2, 4,8} are compared with 4, we obtain two subsets: {2} and {5,8}. The procedure will be repeated for the set {5,8). In the end, all the sets will have no more than one element and we are done. Question: Let X be the number of comparisons made during the whole sorting process. Compute E[X] and show E[X] ~ 2n log n for large n. ber y2 =