Plan an algorithm that finds k smallest numbers

Assignment Help Computer Engineering

Reference no: EM1327714

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.

Reference no: EM1327714

Questions Cloud

Explain how does the selection of sap modules change : How does the selection of SAP modules change the overall implementation project as defined in the ASAP methodology?

Manager-s leadership style influence effectiveness : How does a manager's leadership style influence his or her effectiveness in the workplace? Provide a specific example.

Future value of ordinary annuity investment : What is the future value of this ordinary annuity investment? Does the present value of the investment indicate that this is possible? Your job is to provide an answer to both questions.

The interpersonal relationships in the workplace important : Why are interpersonal relationships in the workplace important?

Plan an algorithm that finds k smallest numbers : plan an algorithm that finds k smallest numbers of the whole G sorted in ascending order and has time complexity O(m*lg(m)) and spatial complexity O(m).

Training needs assessment : Training needs assessment - Explain the problem and examine the needs (using the analyses above)

Calculating present values of cash flows : You can purchase property today for $3.3 million and sell it in 5 years for $4.3 million. (You earn no rental income on the property.)

Bureaucratic costs increase : Given an example of how and why do bureaucratic costs increase a company goes.

Essay-environmental factors impact managers and leaders : The topic for the assignment is to discuss - How do environmental factors impact managers and leaders of organizations?

User Account

All Pages