Share
Explore BrainMass

Design and Analysis of Algorithms

Consider a set G consisting of m integers.

a) Design an algorithm that finds and gives as output the k smallest numbers of the whole G sorted in ascending order and has time complexity O(m*lg(m)) and spatial complexity O(m).

Note: lg denote the logarithm base 2.

b) Design an algorithm that solves the above problem using a mandatory heap and has time complexity O(m + k*lg(m)) and space complexity O(m).

In response give either pseudocode or the description of the steps of the algorithm and justify the complexities.

Solution Preview

Please note that the explanation in this response is rather verbal as the solutions in this response make (complete/partial) use of standard/well-known sorting algorithms.

(a) We can use Merge Sort to sort the given set G of m integers (stored in an array of size m) in increasing order.
Merge Sort guarantees O(m*lg(m)) time complexity.

We will use another array of size m to store the result of merging at any merging step in the merge sort, which will ensure no shifting of elements in same array during merging, rather writing the merged subsequences into temporary array as the elements are being merged and later copy the merged content to the ...

Solution Summary

The explanation in this response is rather verbal as the solutions presented in this response make (complete/partial) use of standard/well-known sorting algorithms.

$2.19