Every night, Verizon 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. Verizon 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 3x 10-7n2, 10-5n log2 n, and 2 x 10-n seconds respectively on a single processor 11. What is the smallest problem size no such that algorithm B is strictly faster than algorithm A for all n 2 no? (Hint: I don't know of an analytical solution to this problem, so try plugging in values for n or use Newton's method.) Justify your approach. 12. What is the smallest problem size ni for which algorithm C is strictly faster than algorithm B for all n 2 n? Justify your approach. 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. 4. 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? Every night, Verizon 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. Verizon 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 3x 10-7n2, 10-5n log2 n, and 2 x 10-n seconds respectively on a single processor 11. What is the smallest problem size no such that algorithm B is strictly faster than algorithm A for all n 2 no? (Hint: I don't know of an analytical solution to this problem, so try plugging in values for n or use Newton's method.) Justify your approach. 12. What is the smallest problem size ni for which algorithm C is strictly faster than algorithm B for all n 2 n? Justify your approach. 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. 4. 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
