5 Deterministic Select: what if you don't like the number 5? In algorithm DeterministicSelect, the input elements are divided into [n/5] groups of 5 elements each (and maybe one group with less than 5 elements). In worksheet 4, we calculated the number of elements that are guaranteed to be smaller than the pivot, and used this fact to derive a recurrence relation that bounds the running time of algorithm DeterministicSelect and establish an O(n) upper bound on the solution of that recurrence. Suppose that, not liking the integer 5, we had decided to divide the input elements into [n/3] groups of 3 elements each instead of [n/5] groups of 5 elements each. 1. [2 marks] How many element are guaranteed to be than the pivot? Justify your answer. 2. [2 marks] Derive a recurrence relation that bounds the running time of this new version of algorithm DeterministicSelect. 3. [3 marks] Guess the best upper bound you can on the solution of the recurrence derived in part (b), by comparing this recurrence to a similar recurrence that you know how to solve. You do not need a formal proof but you should nevertheless justify your answer. Suppose now that we had decided to divide the input elements into [n/7] groups of 7 elements each. 4. [2 marks] How many element are guaranteed to be than the pivot? Justify your answer. 5. [2 marks] Derive a recurrence relation that bounds the running time of this new version of algorithm DeterministicSelect. 6. [3 marks] Guess the best upper bound you can on the solution of the recurrence derived in question 5.5. You do not need a formal proof but you should nevertheless justify your guess. 5 Deterministic Select: what if you don't like the number 5? In algorithm DeterministicSelect, the input elements are divided into [n/5] groups of 5 elements each (and maybe one group with less than 5 elements). In worksheet 4, we calculated the number of elements that are guaranteed to be smaller than the pivot, and used this fact to derive a recurrence relation that bounds the running time of algorithm DeterministicSelect and establish an O(n) upper bound on the solution of that recurrence. Suppose that, not liking the integer 5, we had decided to divide the input elements into [n/3] groups of 3 elements each instead of [n/5] groups of 5 elements each. 1. [2 marks] How many element are guaranteed to be than the pivot? Justify your answer. 2. [2 marks] Derive a recurrence relation that bounds the running time of this new version of algorithm DeterministicSelect. 3. [3 marks] Guess the best upper bound you can on the solution of the recurrence derived in part (b), by comparing this recurrence to a similar recurrence that you know how to solve. You do not need a formal proof but you should nevertheless justify your answer. Suppose now that we had decided to divide the input elements into [n/7] groups of 7 elements each. 4. [2 marks] How many element are guaranteed to be than the pivot? Justify your answer. 5. [2 marks] Derive a recurrence relation that bounds the running time of this new version of algorithm DeterministicSelect. 6. [3 marks] Guess the best upper bound you can on the solution of the recurrence derived in question 5.5. You do not need a formal proof but you should nevertheless justify your guess