Binary Search vs. Sequential Search / Break-even Point [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

I'm really struggling with this homework question. My professor does a terrible job of explaining anything. Help?

There is a trade-off between sorting a list and then using binary search versus just using sequential search on an unsorted list. The choice depends on how many times the list will be searched. Assume that sequential search requires n comparisons in worst case, sorting requires n*log n comparisons, and binary search requires log n comparisons in worst case (where log is log base 2, as we have discussed). Given an unsorted list of 1024 elements (i.e. log 1024 = 10), how many searches s would be required for sorting to be worthwhile? Suppose we consider the average case for sequential search requires n/2 comparisons. Now what is the break-even point for s?

Hint: Write an expression for the number of comparisons required for s searches by each method; then set them equal and solve for s.

Answer 1

You are comparing the time that is needed to perform an initial sort (cost: n*log(n)) and subsequent binary search (cost: log(n)). So, if you want to search s times, you will pay an initial n*log(n) to sort the list and log(n) for each (binary) search. That is to say:

c1 = (n*log(n)) + (s*log(n)) = (n+s)*log(n)

Instead, if you perform linear search, there is no "initial cost", but each search will cost you n, so for s searches:

c2 = s*n

Obviously, for s and n small enough, c2 is smaller because there is no such initial cost, but it grows faster than c1. At a certain point c1 and c2 will cross. That is to say, c1 = c2.

                                                                     n * log(n)
s * n = (n + s) * log(n) --> s * (n - log(n)) = n * log(n) --> s = ------------
                                                                     n - log(n)

Well, you now have to discuss the equation above. This plot should tell you everything:

Answer 2

As a hint: the work done to sort n and then do k binary searches is given by

n log n + k log n

and the work required to do k sequential searches is

n k

If n = 1,000, for what value of k will the second quantity be smaller than the first?

Hope this helps!