the american museum of natural history in new york city contains more than 32 mi
ID: 3804439 • Letter: T
Question
the american museum of natural history in new york city contains more than 32 million specimans and artifacts in its various collections, including the worlds largest collection of dinosoar 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
b. Assuming the inventory is sorted, about how much time would a binary search require?
Explanation / Answer
A. 32 million= 32000000
a computer can check 12000 items in a second so it can check 32000000 in
3200000/12000= 2667 seconds
= 44 min
On average it will take 44/2=22 min assuming the item to be searched is in middle of list.
B.
binary search runs in 0(log n) i.e log232000000 = 25 so at most it will have to look at only 25 entries to find the element.
since our computer takes 1 sec for 12000 comparisons so it will take 1/12000 seconds for doing 1 comparison
so for doing 25 comparisons= 25x(1/12000) = 2 x10^-3 = 2milliseconds
answer: binary search wil require 2 ms.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.