Comparison-based sorting algorithm

Assignment Help Basic Computer Science

Reference no: EM13968268

1. Prove that any comparison-based sorting algorithm requires 0.(N log N) compar- isons on average.

2. We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input is 8, 4, 1, 6, and K is 10, then the answer is yes (4 and 6). A number may be used twice. Do the following:

a. Give an O(N2) algorithm to solve this problem.

b. Give an O(N log N) algorithm to solve this problem. (Hint: Sort the items ?rst. After that is done, you can solve the problem in linear time.)

c. Code both solutions and compare the running times of your algorithms.

Reference no: EM13968268

Questions Cloud

In the context of single period inventory management : Direct Air operates a 300 seat jet from Toledo to Myrtle Beach, SC once a week. Cancellation distribution is normal with mean 30 and s.d. 8. A vacant seat in the jet is considered to cost $600 for the airline. What is the cost of shortage (in the con..

Determining the three-way comparisons : M is an N-by-N matrix in which the entries in each rows are in increasing order and the entries in each column are in increasing order (reading top to bottom). Consider the problem of determining if x is inM using three-way comparisons (i.e., one ..

Linear programming model-production and transportation costs : Linear Programming Model- Forbelt Corporation has a one-year contract to supply motors for all refrigerators produced by the Ice Age Corporation. Ice Age manufacturers the refrigerators at four locations around the country: Boston, Dallas, Los Angele..

Differentiate cosmological models on the nature : Objective: Differentiate cosmological models on the nature of the universe. Assignment Instructions: The Big Bang theory has today largely superseded the Steady State theory

Comparison-based sorting algorithm : 1. Prove that any comparison-based sorting algorithm requires 0.(N log N) compar- isons on average.

Focusing on improving health care delivery : It is increasingly clear that focusing on improving health care delivery is not suf?cient to reduce health disparities. How can we as a society begin to affect the broader factors that underlie racial and ethnic disparities in health?

Cost is irrelevant to the aggregate production plan : Which one of the following cost is irrelevant to the aggregate production plan?

Convey to her superiors using all of the proper channels : Lisha is an engineer at a robotics lab who has discovered that the CEO of her company has been embezzling money from the company for years. She had sufficient evidence of the crime, which she tried to convey to her superiors using all of the proper c..

Optimized version of quicksort : 1. Implement an optimized version of quicksort and experiment with combinations of the following: a. pivot: ?rst element, middle element, random element, median of three, median of ?ve

User Account

All Pages