Every night, AT&T has to update its database of every customer’s telephone number. To enable fast lookups, the database includes an index that is a sorted list of all its phone numbers. This index must be rebuilt each night by re-sorting the contents of the database. AT&T has hired you as a consultant to analyze their computing needs for the nightly sorting run. After carefully checking GitHub, you have found three sorting algorithms – A, B, and C – that can sort n phone numbers in 4 × 10−6n 2 , 10−4n log2 n, and 1.4 × 10−4n seconds respectively on a single processor.

11. What is the smallest problem size n0 such that algorithm B is strictly faster than algorithm A for all n ≥ n0? (Hint: Plugging in values for n or using Newton’s method are acceptable ways to solve the problem, and you are welcome to use online tools such as Wolfram Alpha and Desmos.) Explain your reasoning.
12. What is the smallest problem size n1 for which algorithm C is strictly faster than algorithm B for all n ≥ n1? Explain your reasoning.
13. Describe how to construct a sorting algorithm that always achieves the best running time of any of algorithms A, B, or C for a given n.
14. Suppose the phone database contains 108 phone numbers. The updated information arrives at 4 AM, and the company demands that the new database be ready for use by 5 AM, i.e. one hour later. To meet this deadline, you may split the database evenly across k processors and sort each part separately. (For this problem, ignore the cost of putting the pieces back together.) How many processors do you need to meet your deadline with each of algorithms A, B, and C?