binary search is much more efficient than linear search, with two caveats: (1) T

Question

binary search is much more efficient than linear search, with two caveats: (1) The list must already be sorted for binary search to work.

(2) For very short lists it's harder to say which algorithm is faster.

For this problem, you will quantify the performance difference

between the two. For this example, make the following assumptions:

1. We have an unsorted list of 256 items.

2. Sorting the list costs 4480 time units.

3. Each loop iteration of a linear search costs 1 time unit.

4. Each loop iteration of a binary search costs 4 time units.

If you only want to do one search in the list, it's clearly not worth sorting the list then running binary search, because the cost of

sorting is far higher than the cost of a single linear search.

How many searches for items that are not in the list would you have to do to make sorting and using binary search a better strategy than using linear search?

Also write down a few sentences to explain how you calculated your answer. Do not write any code!!!!

Your answer:

Explanation / Answer

costs 4480 time units
x items= x*256*1
time for 1 binary search = No of loop iterations*time taken by each iteration
No of loop iterations for binary search for each search=(log(base 2)256)
h x items= x*4*(log(base 2)256)*1
t=4480
x items= 4480 + x*4*(log(base 2)256)*1
x*256 > 4480+x*4*8
256x-32x>4480
224x>4480
x>20

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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