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 points

Answer 1

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) !