At the end of Section 3.4.2 (of Invitation to Computer Science, 7th edition), we

Question

At the end of Section 3.4.2 (of Invitation to Computer Science, 7th edition), we talked about the trade-off between using sequential search on an unsorted list as opposed to sorting the list and then using binary search. If the list size is n = 100,000, about how many worst-case searches must be done before the second alternative is better in terms of number of comparisons? (Hint: Let p represent the number of searches done and assume selection sort would be used to sort the list before using binary search.)

Explanation / Answer

Sequential search

For sequential search, say if the element is not present on the unsorted list, the number of comparisons would be equal to n+1 = 100,001. This is because every element in the list would be traversed once and there will be a comparison involved for every element in the list. Finally, while exiting the loop, there will be another condition-check. Hence, the above answer,

Selection Sort + Binary Search

For selection sort algorithm done before binary search, the number of comparisons would be n^2 for average and worst case. Hence the number of comparisons would be approximately 100000^2, which 10^10.

Now, the list is sorted and the worst case complexity of binary search is (log n) = log 100000 ~ 17.

The total number of comparisons including selection sort + binary search becomes approximately (10^10 + 17) or 10^10 + p (as given in the hint), which is way higher than the number of comparisons done in linear search (only 100,001).

To conclude, binary search is efficient only when the list is already sorted. Sorting and then performing binary search is highly inefficient than linear search, since even the most efficient sorting algorithms have a time complexity O(n log n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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