Question

Random Pivot Selection: In the algorithm input elements are divided into groups of 5.

a) Will the algorithm works if they are divided into groups of 7? Using the substitution method prove your claim by arriving at the running time similar to the recurrence we got for group size 5 during the lecture
b) Show that SELECT does not run in linear time if groups of 3 are used using the substitution method

Answer 1

A) The algorithm will work if they are divided into groups of 7

B ) If the groups of 3 are used they do not run in Linear time

Step-by-step explanation:

ATTACHED TO THIS IS THE DETAILED PROVE OF why the algorithm will work if they are divided into groups of 7 and also the prove that if groups of 3 are used they do not run in Linear time