How will you choose so that the modified algorithm

Assignment Help Computer Engineering

Reference no: EM132141255

Suppose PARTITION function of QUICKSORT algorithm always produces 9 : 1 proportional split (i.e., after partition, one sub-array contains n/10 elements and the other sub-array contains 9n/10 elements). To take advantage of the fact that insertion sort works really well on arrays of small size, suppose we make the following modification in QUICKSORT algorithm. Whenever any sub-array has k or fewer elements, we call INSERTION SORT and return the answer to the top level QUICKSORT call.

(a)Show that this modified algorithm runs in O(nk + n log(n/k)) time. ( Hint: How many times PARTITION function need to be called? How many times INSERTION SORT needs to be called? Note that worst case running time of INSERTION SORT on an array of n elements is O(n^2 ).)

b)How will you choose so that the modified algorithm will have O(n log n) running time? Show your work.

(c)Suppose PARTITION function always produces a split where one of the sub-arrays has exactly one element in it. In this case, what will be running time of the modified algorithm in terms of n and k? Can you choose an appropriate value of k so that the modified algorithm will run in O(n log n) time? Show your work.

Reference no: EM132141255

Questions Cloud

Compare the time for a query and response : Compare the time for a query and response for a complete DNS query and response (to all required nameservers) if M=1, M=2, and M=3.

How many 2 gb hard disks do you need if the hard disk : How many 2 GB hard disks do you need if the hard disk should store up to 70% of their capacity using RAID 0, RAID 1, RAID 3, or RAID 5.

What is the running time of your algorithm : What is the running time of your algorithm? Your program will take as input a file with edge information.

Write a program in c that shows the coach : Write a program in C that shows the coach, the total number of different pairs he can choose in the team.

How will you choose so that the modified algorithm : How will you choose so that the modified algorithm will have O(n log n) running time? Show your work.

How can we quickly test if k is even : We say that k is even if and only if |k| mod 2 = 0. How can we quickly test if k is even without using arithmetic operations, and without using mod?

Describe the ways in which this is an example of attacks : Suppose you are doing some online banking using your bank's website. An attacker has set up an active wiretap between your computer and your bank's server.

Forecasted an expected return : Using the data from problem 1, if you forecasted an expected return of 16.00% for stock XYZ, is it overvalued, undervalued, or fairly valued? Briefly, why?

Compare the time for a query and response for a complete : Compare the time for a query and response for a complete DNS query and response (to all required nameservers) if M=1, M=2, and M=3.

User Account

All Pages