1) . Let L be a sorted list of size 1000. In the worst case, to determine whethe

Question

1)

. Let L be a sorted list of size 1000. In the worst case, to determine whether an element x is in L, what is the minimum number of comparisons made by a comparison-based search algorithm?

2)

uppose that L is a list of 10,000 elements. Find the average number of comparisons made by bubble sort, selection sort, and insertion sort to sort L.

3)

Let L be a list of 1024 distinct elements. Suppose L is sorted using a comparison-based algorithm. In the worst case, what is the minimum number of key comparisons to sort L?

4) Suppose that L is a list of 10,000 elements. Find the average number of comparisons made by quick sort and merge sort to sort L.

Explanation / Answer

1) The worst case scenario of searching an element existance in the list L is SRH(n) = (log2(n+1))

srh(1000) = log2(1001) = 9.967

2) Average case for bubble sort comparison is n^2 = (10000)^2 = 10^8

Average case for selection sort comparison is n^2 = (10000)^2 = 10^8

Average case for Insertion sort comparison is 1/4(n^2 - n) = 1/4(10^8 - 10000) = 24997500

3) the formula is nlog(z) where z = sort by another sort example lets take merge sort

1024log(n^2) = 1024 log 1048576 = 1024 * 6.02 = 6165

4) For both the cases of merge sort and quick sort the average comparison is = n*logn = 10000 * log 10000 = 99000

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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