QuickSort is asymotivaly faster than bubblsort Quicksort is asymptotically faste
ID: 3825311 • Letter: Q
Question
QuickSort is asymotivaly faster than bubblsort
Quicksort is asymptotically faster than bubblesort In the worst case On average b. Quicksort is asymptotically slower than mergesort In the worst case On average c) To sort 8 numbers it is necessary to make at least 16 comparisons 17 comparisons 18 comparisons d) To find 2 heavier coins among 14 same coins using lever scales it is necessary to make at least 4 comparisons 5 comparisons e) To find 2 heavier coins among 15 same coins using lever scales it is necessary to make at least 4 comparisons 5 comparisons Given set S of points in the Euclidean plane. Voronoi graph of S always contains MST of S has at most 3.16*|S| edges has at most 3.1 * |S| edges has at most 2.75*|S| edges has at most 2.85*|S| edges has at least S edges has at least |S|H edges contains edge connecting closest pair of points g) Given set S of points in the Euclidean plane, convex hull of S always contains MST of S has at most 2.5*|S| edges has at least 1.05*|S| edges contains edge connecting closest pair of pointsExplanation / Answer
a) Quicksort is asymptotically faster than bubblesort
Answer:
In the worst case --------- No
On average ------------- Yes
Explanation :
Quick sort takes O(n log n) comparisions on an average.
In the worst case O (n 2) for both sorting techniques.
b) Quicksort is asymptoticallly slower than mergesort
Answer:
In the worst case ------ Yes
On average --------- No
Explanation:
Merge sort takes O(n log n) comparisions on in any case.
In the worst case O (n 2) for quick sort.
c) To sort 8 numbers it is necessary to make at least
Answer:
16 comparisions ------ Yes
17 comparisions ----- Yes
18 comparisions ------ Yes
Explanation:
It depends on the sorting algorithm which is used.
O( n 2 ) in the worst case.
d) To find 2 heavier coins among 14 same coins using lever scales it is necessary to make at least
4 comparisions ------ Yes
5 comparisions ----- Yes
Explanation :
You should use the following formula to get the actual value
( r + n - 1 ) !
----------------
r ! (n-1) !
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.