Consider these recurrences, defining M(n) and S(n) for all integers n0: if n M(n) = {M([n/2])...

 

Transcribed Image Text:

Consider these recurrences, defining M(n) and S(n) for all integers n0: if n M(n) = {M([n/2]) + M([n/2]) + n 1 otherwise. S(n) = {M(n) if n < 140, 6. [n/5] + S([n/5]) + S(6 + [7n/10]) otherwise. M(n) is the worst-case number of comparisons used by MERGE-SORT on n items, and S(n) is (roughly) the worst case number of comparisons used by SELECT on n items (see Section 9.3). From the book we know that M(n)=O(n lg n) and S(n)=(n), so eventually S(n) is much smaller than M(n). Write a computer program finding the first n such that 2*S(n) < M(n). It should print n, S(n), and M(n). Turn in a copy of your program, and its output. Remarks: the first n with S(n) Consider these recurrences, defining M(n) and S(n) for all integers n0: if n M(n) = {M([n/2]) + M([n/2]) + n 1 otherwise. S(n) = {M(n) if n < 140, 6. [n/5] + S([n/5]) + S(6 + [7n/10]) otherwise. M(n) is the worst-case number of comparisons used by MERGE-SORT on n items, and S(n) is (roughly) the worst case number of comparisons used by SELECT on n items (see Section 9.3). From the book we know that M(n)=O(n lg n) and S(n)=(n), so eventually S(n) is much smaller than M(n). Write a computer program finding the first n such that 2*S(n) < M(n). It should print n, S(n), and M(n). Turn in a copy of your program, and its output. Remarks: the first n with S(n)