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

suppose we do N searches

now for linear

so for searching 1 element not present in the list

we take 256 timeunit

so for N searches

total time is 256N

now for binary

no of loop will be

2^n = 256

n= 8

so time taken will be 8x4 = 32 time unit

now for unsorted list

it is 4480 + 32* N

so now

4480 + 32N < 256 N

4480 < 224N

N> 20

hence it should be greater than 20 searches

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

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