For some problems, it is convenient to have data in already sorted order. For ea
ID: 3791265 • Letter: F
Question
For some problems, it is convenient to have data in already sorted order. For each of the questions below explain whether sorting the list helps to solve a problem faster. If yes, explain how sorting helps performance in terms of running time. If not, describe a faster alternative algorithm without sorting along with its runtime complexity. (Note that you must take into consideration the runtime for sorting the list first)
1. Finding the mth smallest number in a list
2. Computing the mode of a set of integers (e.g., the value that occurs most often).
3. Computing the median of two arrays. (let me rephrase: You have some numbers in both arrays, you need to find a median for all the numbers combined).
4. Checking whether a particular item exists more than once in the array.
5. Find the minimum value in an array.
Explanation / Answer
Hi, I have answered Q1.
Please repost others in separate post.
Please let me know in case of any issue.
Q1.
Yes sorting can help to improve the time complexity of this algorithm,
sort the given array using a O(nlogn) sorting algorithm like Merge Sort, Heap Sort, etc and return the element at index k-1 in the sorted array. Time Complexity of this solution is O(nLogn).
// Function to return k'th smallest element in a given array
int kthSmallest(int arr[], int n, int k)
{
// Sort the given array
sort(arr, arr+n);
// Return k'th element in the sorted array
return arr[k-1];
}
We can also improve time complexity little bit.
We can also use Max Heap for finding the k’th smallest element. Following is algorithm.
1) Build a Max-Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the k’th element (arr[k] to arr[n-1]), compare it with root of MH.
……a) If the element is less than the root then make it root and call heapify for MH
……b) Else ignore it.
// The step 2 is O((n-k)*logk)
3) Finally, root of the MH is the kth smallest element.
Time complexity of this solution is O(k + (n-k)*Logk)