Searching Algorithm - Which to use for this problem? ---------------------------

Question

Searching Algorithm - Which to use for this problem?

-----------------------------------------------------------------------------

The original problem was:

You get a job with a small e-commerce company.

b) The customer base has grown to 8,000,000 customers. Jorge now insists that the sorting algorithm must be as fast as possible in all cases, but the algorithm may now use up to 50,000,000 bytes of additional memory. Each reference to a customer record takes up 4 bytes. Which of the sorting algorithms (merge sort or quick sort) could you use in this situation? Explain your answer. (**I already chose merge sort, which is correct**)

-------------------------------------------------------------------------------------------

****What I need to know is the answer for (a) and (b) below****

-------------------------------------------------------------------------------------------

One reason Jorge wants to sort the list is to be able to search for a customer record efficiently.

a) In the worst case, how many comparisons will it take to search for a customer record in an unsorted list of 8,000,000 customer records? Explain your answer. Which searching algorithm would you use?

b) After the list has been sorted, how many comparisons will it take to search for a customer record? Explain your answer. Which searching algorithm would you use?

Explanation / Answer

a) The worst case would require us to make 8,000,000 comparisons.

This is because we have to iterate the customer records from the start and compare each one to the record which we are searching, because we have no additional information about the order in which nodes are stored.

The algorithm which we will use is Linear Search. It's complexity would be O(n), where n is the total no of customer records which we have. The worst case with this complexity would occur when we find the element at the last index of the stored records or don't find the element at all.

b)  The worst case for this case would occur when the searched element is not present in the stored customers and is lesser/greater than all customer records(according to the sorting condition).

We will use the binary search algorithm for the sorted storage.which has a complexity of O(log(n)). This is because a sorted list can be divided into two subparts from the middle of the list and we can apply the divide and conquer paradigm to recursively carry our search in one of the two sublists, thus significantly reducing our running times.

The maximum number of compaisons which we will make is 2*log_2(8000000-1) which is equal to 46 comparisons. This is becausein each step the list is being cut into two parts, each of the size (n-1)/2, we have a maximum of log_2(n-1) steps.This leads to a total of 2*log_2(n-1) comparisons, which asymptotically indeed equals to O(log(n)).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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