We want to compare the worst-case complexity of the sorting algorithms InsertionSort, MergeSort, HeapSort, andQuickSort as studied in this course. However, we want to compare their worst-case efficiencies when applied to sorting arrays with restricted element types. More specifically, suppose A[1..n] is an array of n elements, where each element is a single decimal digit 0 to 9. In this case, the worst-case most efficient sorting algorithm is

a. MergeSort

b. QuickSort

c. InsertionSort

d. HeapSort

Given an array A[1 .. n] of n arbitrary real-valued elements, we want to determine whether there is a real number that occurs in the array more than n/3 times. The worst-case most efficient way to solve this problem is to use

a. selection

b. None of the other choices.

c. sorting

d. an incremental method similar to that of the VLSI Chip Testing problem solution

We are given the equation 3x+5y=7 of a line L in the plane. We are also given a set X of m arbitrary real numbers and a set Y of n arbitrary real numbers. The problem is to determine whether there is any point on line L whose x-coordinate is in set X and its y coordinate is in set Y. This problem can be solved most efficiently in the worst-case in ( ? ) time.

a. (m+n)log(m+n)

b. m+n

c. None of the other choices

d. m*n

We are given a collection S of n points in the two dimensional plane, each point with integer x, y coordinates between 1 and n. We want to sort the points in S in ascending order of their Euclidean distance from the origin. This can be accomplished most efficiently in the integer RAM model, in the worst-case time ( ? ).

a. nlogn

b. n

c. n^2

d. n^2logn