8. Breaking bag. A bag is an abstract data type which may hold any number of objects. You may query the bag to determine how many objects are in the bag. This takes constant time. You may also apply the probabilistic operation split to a bag, which partitions the objects in the given bag into two new bags. All you know about split is that for every pair of objects in the input bag, the probability that both objects end up in the same output bag is < 1/2. Also, if a bag contains n objects, applying split to the bag takes time O(n). 3 Your goal is to design and analyze a probabilistic algorithm that takes as input a bag containing n objects and produces as output n bags such that each output bag contains a single object. The ordering of the output bags is irrelevant. Your algorithm should run in expected time O(nlogn). Here is an outline you should follow: (a) The algorithm is the obvious divide and conquer algorithm, using the split operation to get two sub- problems, and then recursing on both, as necessary. Write out this algorithm. (b) To analyze the running time, consider any two objects in the original bag, and argue that after d levels of recursion, the probability that they remain in the same bag is at most 2-d. (c) Using (b), argue that for any particular object in the original bag, the probability that it is not in a bag by itself after d levels of recursion is at most 2-d(n - 1). Hint: union bound. = (d) Using (c), show that for any particular object i in the original bag, if Di is the depth in the recursion tree at which i ends up in a bag by itself, then E[Di] O(logn). Hint: use the tail sum formula E[Di] = d>1 Pr[Di d]. (e) Finally, argue that the running time T is O(i (Di + 1)), where the sum is over all objects i in the original bag, and from this and part (d), argue that E[T] = O(nlogn). Hint: linearity of expectation.