Find the optimum value of k and compare the result

Assignment Help Data Structure & Algorithms

Reference no: EM132106248

Processing time of InsertionSort is c · n2. To merge k pre-sorted subarrays that contain together n items you have to compare the k top items in all the sub- arrays to choose the current maximum item and place it into the sorted array (assuming that all the items have to be sorted in ascending order).

Therefore, the time for merging is proportional to (k - 1) · n.

Let the processing time of the merge be c · (k - 1) · n where the scale factor has the same value as for InsertionSort. Analyse whether it is possible to accelerate sorting of n items in the following way:

-Split the initial array of size n into k subarrays of size n/k. The last subarray may be longer to preserve the total number of items n but do not go in such details in your analysis.

-Sort each subarray separately by InsertionSort.

-Merge the sorted subarrays into a final sorted array.

If you have found that the acceleration is possible, then find the optimum value of k and compare the resulting time complexity of this sorting algorithm to that of InsertionSort and MergeSort.

Reference no: EM132106248

Questions Cloud

What aspect of adolescent thinking is danica experiencing : Danica woke up and had a pimple on her cheek. She pretended to be sick so she didn't have to go to school because she was sure everyone was going to see

What psychological phenomenon does filter theory help : What psychological phenomenon does filter theory help explain ? give a real-life example of the kind of stimuli that are allowed through the filte

How does the processor know which function to execute : What is the only place, other than the function definition,that the name of the function used as the service routine is given in the source code of your project

Amount of hormone the fetus : Do you believe some of the differences we see are differences in the amount of hormone the fetus is exposed

Find the optimum value of k and compare the result : The last subarray may be longer to preserve the total number of items n but do not go in such details in your analysis.

Clear threat of violence towards someone : What are some points that should be considered if a client makes a clear threat of violence towards someone?

What is the ethical issue described in the scenario : Question: What is the ethical issue described in the scenario? Why is this an ethical issue?

Does professor amongus deserve the turing award : Professor Amongus has just designed an algorithm that can take any graph G with n vertices and determine in O(nk)time whether G contains a clique of size k.

Discuss the specific therapy : Choose ONE of the disorders and discuss the specific therapy (i.e., Cognitive Behavioral Therapy, Psychoanalysis, etc.) that you think may work best in treating

User Account

All Pages