Reference no: EM132403162

Exercise.

We have been told to develop an algorithm to fins a subset of sorted elements within a bigger set. Our customer does not care about how the algorithm is implemented as far as it is as quick as possible.

Therefore, we devise two methodologies we could use. To check which of these is the most efficient, we consider that we have an unsorted price list of 10¹⁰ distinct products and that we want to find the 5000 most expensive on that list.

The two algorithms we have come up with are the following:

• Algorithm 1: repeat a sequential search (complexity O(n)) between the 10¹⁰ elements tofind the most expensive element on the list, for each of the 5000 elements we want to find.

• Algorithm 2: convert the list to an array (complexity O(n)), sort the array by cost in descending order (complexity O(n log n)) and return the first 5000 elements.

Before choosing which of the two algorithms is the most suitable, we have to take into account the following conditions:
• Looking up 100 elements in an unsorted list costs 0,15 ms.
• Sorting 100 elements costs 0, 15 ms.

You can consider the fact of accessing memory data to cost 0 ms.

Therefore, taking into account these conditions, which of the two algorithms you think is the most afficient? Justify your answer.