Design and Analysis of Algorithms
Not what you're looking for?
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.
Purchase this Solution
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.
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 ...
Purchase this Solution
Free BrainMass Quizzes
Word 2010: Table of Contents
Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.
C# variables and classes
This quiz contains questions about C# classes and variables.
C++ Operators
This quiz tests a student's knowledge about C++ operators.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
Javscript Basics
Quiz on basics of javascript programming language.