PLEASE SOLVE COMPLETELY AND SHOW ALL STEPS.

Problem 3. Assume you execute quicksort using the version of partition from CLRS. We are inter- ested in the exact fewest number of comparisons quicksort will do as a function of n (i.e., its best case). Asume 2 where k is a natua nmber) (a) (i) Give an example with n 3 that does as few comparisons as possible. (ii) Give an example with n-7 that does as few comparisons as possible. (iii) Give an example with n-15 that does as few comparisons as possible. b) We might guess that the number of comparisons is approximately nlg(n+1)-2n. (Why?) Create a table with a column for n1,3,7,15; a column with the exact number of comparisons for quicksort in the best case; a column with the value of the approximate guess, n lg(n + 1)-2n; and a column with the difference between the exact value and the approximate guess. (c) Using the information from the above table give an exact formula for the number of comparisons. d) Write a recurrence for the number of comparisons in the best case as a function of n. (You may use your notes from class.) (e) Use mathematical induction to prove that your formula is a solution to the recurrence. Problem 3. Assume you execute quicksort using the version of partition from CLRS. We are inter- ested in the exact fewest number of comparisons quicksort will do as a function of n (i.e., its best case). Asume 2 where k is a natua nmber) (a) (i) Give an example with n 3 that does as few comparisons as possible. (ii) Give an example with n-7 that does as few comparisons as possible. (iii) Give an example with n-15 that does as few comparisons as possible. b) We might guess that the number of comparisons is approximately nlg(n+1)-2n. (Why?) Create a table with a column for n1,3,7,15; a column with the exact number of comparisons for quicksort in the best case; a column with the value of the approximate guess, n lg(n + 1)-2n; and a column with the difference between the exact value and the approximate guess. (c) Using the information from the above table give an exact formula for the number of comparisons. d) Write a recurrence for the number of comparisons in the best case as a function of n. (You may use your notes from class.) (e) Use mathematical induction to prove that your formula is a solution to the recurrence