The American Museum of Natural History in New York City contains more than 32 mi
ID: 3875960 • Letter: T
Question
The American Museum of Natural History in New York City contains more than 32 million specimens and artifacts in its various collections, including the world's largest collection of dinosaur fossils. Many of these are in storage away from public view, but all must be carefully inventoried. a. Suppose the inventory is unordered (!) and a sequential search is done to locate a specific artifact. Given that the search is executed on a computer that can do 12,000 comparisons per second, about how much time on the average would the search require? b. Assuming the inventory is sorted, about how much time would a binary search require?Explanation / Answer
1. Inventory is unordered and sequential search is doing so time complexity in average case is :
Average number of comparisons done by sequential search is (N+1)/2
it is approx to 32 million /2 = 16 million
in one second 12000 comparisions
16 million is equal to 16000 thousand
one second 12 thousand comapision
16000/12 = 1333/1334 seconds approx to 22 mins
2) if sorted and binary search
that is log(n) camparisions
log(32 million) = approx 7.5 seconds
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.