Prove that any comparison-based algorithm to completely sort

Assignment Help Computer Engineering

Reference no: EM133703763

Lower bound for k-sorted arrays

We say that an array A[1..n] is k-sorted if it can be divided into k blocks, each of size n/k, such that the elements in each block are larger than the elements in earlier blocks, and smaller than elements in later blocks. The elements within each block need not be sorted

For this problem, you may assume that k divides n evenly.

(a) Write down the pseudocode for an algorithm that completely sorts an already k-sorted array of n elements in O(n log(n/k)) time. Write down the pseudocode, analyze its running time and explain why it correctly sorts a k-sorted array. 1

(b) Prove that any comparison-based algorithm to completely sort a k-sorted array requires ?(n log(n/k)) comparisons in the worst case, i.e., that your algorithm in part (a) is asymptotically optimal? Hint: It is not sucient to combine lower bounds to sort individual blocks! Think about how many dierent permutations are possible in a k-sorted array.

Reference no: EM133703763

Questions Cloud

Which of the following rules is a component of hipaa : HIPAA is a federal law that protects patient privacy and prevents unauthorized release of medical Information. Which of the following rules is a component

How has the global economy changed over time : How has the global economy changed over time? Which changes are most important, and why?

Relational database relate to one another : Access versus using a spreadsheet. Write a sentence to explain how the terms field, record, table, and relational database relate to one another

Cost-effectiveness-system effectiveness are considerations : Cost-effectiveness and system effectiveness are considerations that must be incorporated into a nurse's daily practice.

Prove that any comparison-based algorithm to completely sort : Write down the pseudocode, analyze its running time and explain why it correctly sorts a k-sorted array

Describe karl marx-his followers with real world communism : Compare or contrast the theoretical communism described by Karl Marx and his followers with the "real world" Communism which developed in the Soviet Union.

Describe how it can help slim and huskys pizza : Talk about Blog posts and Photo and visual galleries as your two types from those suggested in the video. Describe BOTH in detail and then select ONE

Identify skills needed in organization and self-motivation : Identify and utilize skills needed in organization and self-motivation. Demonstrate ability to set and accomplish specific tasks and goals.

What compliance standard requires companies : What compliance standard requires companies to "develop, implement, and maintain a comprehensive written information security program that contains

User Account

All Pages