Question

(20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of size 5. So n/5 groups. (b) Find the median of each group. (c) Find the median x of the n/5 medians by a recursive call to Select. (d) Call Partition with x as the pivot. (e) Make a recursive call to Select either on the smaller elements or larger elements (de- pending on the situation); if the pivot is the answer we are done. Then, the recurrence for the running time was T(n) = T(1/5n) + T(7/10n) + O(n) (Can you explain why?) Now suppose we change the algorithm as follows. (a) Divide the n elements into groups of size 9. So n/9 groups. (b) Find the median of each group. (c) Find the median x of the n/9 medians by a recursive call to Select. (d) Call Partition with x as the pivot. (e) Make a recursive call to Select either on the smaller elements or larger elements (de- pending on the situation); if the pivot is the answer we are done.

Now what is the recurrence for the running time? Also explain how much time it takes to perform each of the five steps.

5. (20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of size 5. So n/5 groups. (b) Find the median of each group. (c) Find the median x of the n/5 medians by a recursive call to Select. (d) Call Partition with x as the pivot. (e) Make a recursive call to Select either on the smaller elements or larger elements (de- pending on the situation); if the pivot is the answer we are done. Then, the recurrence for the running time was T(n) = T(žn) +T(7on) + O(n). Now suppose we change the algorithm as follows. (a) Divide the n elements into groups of size 9. So n/9 groups. (b) Find the median of each group. (c) Find the median x of the n/9 medians by a recursive call to Select. (d) Call Partition with x as the pivot. (e) Make a recursive call to Select either on the smaller elements or larger elements (de- pending on the situation); if the pivot is the answer we are done. Now what is the recurrence for the running time? Also explain how much time it takes to perform each of the five steps.

Answer 1

Time Taken each of the Five steps

Step 1

Dividing the n elements into n/5 group will take constant time i.e)(1)

Step 2

To find median of n elements we need O(n ) time

Sort the above created ⌈n/5⌉ groups and find median of all groups. Create an auxiliary array ‘median[]’ and store medians of all ⌈n/5⌉ groups in this median array.

So here we have groups of only 5 elements so time needed is constant i.e O(1)

so In all Step 1 and Step 2 will take O(n) time

Step 3

We recursively call to find median of median

so Time taken = T(n/5)

Step 4

Is normal Partition algorithm that takes O(n) time

Step 5

What is the worst case size of these recursive calls?

The answer is maximum number of elements greater than median (obtained in step 3) or maximum number of elements smaller than median

At least half of the medians found in step 2 are greater than or equal to median. Thus, at least half of the n/5 groups contribute 3 elements that are greater than median, except for the one group that has fewer than 5 elements. Therefore, the number of elements greater than median is at least.

$3\left (\left \lceil \frac{1}{2}\left \lceil \frac{n}{5} \right \rceil \right \rceil-2 \right )\geq \frac{3n}{10}-6$

So In the worst case, the function recurs for at most n – (3n/10 – 6) which is 7n/10 + 6 elements.

So time needed is T(7n/10 +6) = T(7n+10)

So total Recurrence Relation is

T(n) = T(n/5) + T(7n/10) + O(n)

After solving this relation the time we get is O(n) in worst case

Now change in the algorithm

1. This time we are dividing into groups of 9 elements in O(1) time

2.To find median of each group of n elements take O(n) but here we have 9 elements only so O(1) time

so In all Step 1 and Step 2 will take O(n) time

3.We will recursively call to find median of all groups

So time is T(n/9)
4. Normal Partition Algotihm takes O(n) time

5. Same reason as above bt makes changes accortding to 9 elements now so this time atlest half will be 5 instead of 3 so calculation will be :--->

the number of elements that are less than medOfMed is at least 5n/18 -20

5 ( 1/2 ( n/9 ) - 4 ) >= 5n /18 -20

So In the worst case, the function recurs for at most n – (5n/18 – 20) which is 13n/18 + 20 elements.

so total time = T( 13n/18 )

So total Recurrence Relation is

T(n) = T(n/9) + T(13n/18) + O(n)

After solving this relation the time we get is O(n) in worst case

Thank You

If u like the answer please upvote it