Recall the problem of finding the kth smallest number in an array A[0, N - 1]....

 

Transcribed Image Text:

Recall the problem of finding the kth smallest number in an array A[0, N - 1]. We discussed the MEDIAN- OF-MEDIAN QUICK-SELECT algorithm that can find the number in A in O(N) time. Now, we want to solve the following problem. Given an array A of length N, where N is a power of 2. Assume that A has distinct numbers. Find the smallest number, the 2nd smallest number, the 4th smallest number, the 8th smallest number, the 16th smallest number, and so on until you find the Nth smallest number. a. One way of solving the problem is to find the kth smallest in the array by using the quick-select algorithm for k = 1, 2, 4, 8, 16, . . ., N separately. What is the complexity of this algorithm? b. Now, describe an O(N) algorithm for solving the problem. The following may prove useful in analyzing the complexity: N + N/2+N/4++1 <2N. Recall the problem of finding the kth smallest number in an array A[0, N - 1]. We discussed the MEDIAN- OF-MEDIAN QUICK-SELECT algorithm that can find the number in A in O(N) time. Now, we want to solve the following problem. Given an array A of length N, where N is a power of 2. Assume that A has distinct numbers. Find the smallest number, the 2nd smallest number, the 4th smallest number, the 8th smallest number, the 16th smallest number, and so on until you find the Nth smallest number. a. One way of solving the problem is to find the kth smallest in the array by using the quick-select algorithm for k = 1, 2, 4, 8, 16, . . ., N separately. What is the complexity of this algorithm? b. Now, describe an O(N) algorithm for solving the problem. The following may prove useful in analyzing the complexity: N + N/2+N/4++1 <2N.

Answer rating: 100% (QA)

a Complexity of Individual kth Smallest Calls The quickselect algorithm for finding the kth smallest element in an array has an average time complexit... View the full answer