Question:
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