You must find 1000 most expensive items from an unsorted price list containing 1

Question

You must find 1000 most expensive items from an unsorted price list containing 107 different items. Two schemes of solution are as follows.

Scheme A: repeat 1000 times the sequential search (with the linear complexity O(n)).

Scheme B: convert the list into an array (the same complexity O(n) as for search), then sort the array (complexity O(n log n)) and fetch 1000 top items.

Which scheme would you prefer assuming that searching for 100 items in the unsorted list takes 0.1 millisecond (ms) and sorting of 100 items also takes 0.1 ms? Time for fetching data should not be taken into account.

Explanation / Answer

Answer:

The scaling factors for the linear search and the sort are 0.1 /100 = 0.001 and

0.1/100 log 100 = 1 /200 = 0.0005, respectively (you may use any convenient base of the logarithm for computing the running time).

Then the overall time for the scheme A is TA = 0.001 · 10^7 · 10^3 = 10^7 ms, or 10^4 seconds. The overall time for B consists of the time to convert the list into an array: TB,1 = 0.001 · 10^7 ms, or 10 seconds, and the time for sorting the array:

TB,2 = 0.0005 · 10^7 · log(10^7 ) = 35 · 10^3ms = 35s.

Therefore, the scheme of choice is B.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.