Every night, AT&T has to update its database of every customer's telephone number. To enable fast lookup the database includes an index that is a sorted list of all its phone numbers. This index must be rebu 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. Aft carefully checking GitHub, you have found three sorting algorithms – A, B, and C - that can sort n pho numbers in 3 × 10-7n², 10-5n log2 n, and 1.2 x 10-4n seconds respectively on a single processor. - 11. 12. 13. 14. What is the smallest problem size no such that algorithm B is strictly faster than algorithm for all n ≥ no? (Hint: Plugging in values for n or using Newton's method are acceptable ways to sol the problem, and you are welcome to use online tools such as Wolfram Alpha and Desmos.) Expla your reasoning. What is the smallest problem size n₁ for which algorithm C is strictly faster than algorithm for all n ≥n₁? Explain your reasoning. Describe how to construct a sorting algorithm that always achieves the best running time any of algorithms A, B, or C for a given n. Suppose the phone database contains 108 phone numbers. The updated information arriv at 4 AM, and the company demands that the new database be ready for use by 5 AM, i.e. one ho later. To meet this deadline, you may split the database evenly across k processors and sort ea part separately. (For this problem, ignore the cost of putting the pieces back together.) How ma processors do you need to meet your deadline with each of algorithms A. B. and C?
Every night, AT&T has to update its database of every customer's telephone number. To enable fast lookup the database includes an index that is a sorted list of all its phone numbers. This index must be rebu 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. Aft carefully checking GitHub, you have found three sorting algorithms – A, B, and C - that can sort n pho numbers in 3 × 10-7n², 10-5n log2 n, and 1.2 x 10-4n seconds respectively on a single processor. - 11. 12. 13. 14. What is the smallest problem size no such that algorithm B is strictly faster than algorithm for all n ≥ no? (Hint: Plugging in values for n or using Newton's method are acceptable ways to sol the problem, and you are welcome to use online tools such as Wolfram Alpha and Desmos.) Expla your reasoning. What is the smallest problem size n₁ for which algorithm C is strictly faster than algorithm for all n ≥n₁? Explain your reasoning. Describe how to construct a sorting algorithm that always achieves the best running time any of algorithms A, B, or C for a given n. Suppose the phone database contains 108 phone numbers. The updated information arriv at 4 AM, and the company demands that the new database be ready for use by 5 AM, i.e. one ho later. To meet this deadline, you may split the database evenly across k processors and sort ea part separately. (For this problem, ignore the cost of putting the pieces back together.) How ma processors do you need to meet your deadline with each of algorithms A. B. and C?
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Please do not give solution in image format thanku
Transcribed Image Text: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 3 x 10-7n², 10-5n log2 n, and 1.2 × 10-4n seconds respectively on a single processor.
11. (5 p What is the smallest problem size no such that algorithm B is strictly faster than algorithm A
for all n ≥ no? (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.
13.
14.
What is the smallest problem size n₁ for which algorithm C is strictly faster than algorithm B
for all n ≥ n₁? Explain your reasoning.
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.
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?
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 5 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education