Purchase Solution

Design and Analysis of Algorithms

Not what you're looking for?

Ask Custom Question

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.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

Javscript Basics

Quiz on basics of javascript programming language.