A binary search is not always the fastest way to search a sequentially allocated

Question

A binary search is not always the fastest way to search a sequentially allocated main memory table. First consider tables whose size is less than about 50 items. Explain why a sequential search may be faster if each element in the table has an equal probability of being the desired item. Second explain a method for searching a sequentially allocated table which may be faster than a binary search when the data obeys W. P. Hesing’s “80/20” rule (or a Pareto distribution). How might tables fitting the “80/20” rule adjust their selves over time if the reference frequency for table contents is subject to change?

Explanation / Answer

Solution:

In a table where the probability of finding each element is same the sequential or linear search will perform best since we can directly access the index at which the value is present, it can give us the time complexity of as good as O(1).

If data is obeying 80/20 rule, this means 20% of the fields in the table are empty fields then binary search won't be able to decide which way to go when the compared item in the table is NULL, then it will probe to the left or right and make a decision, that is why here the binary search won't be as effective compared to the sequential search.

To adjust as the data is increasing in the table the table size needs to increase in the same ratio of 8-/20 rule since we are following it.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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