8. Use the substitution method to prove that the recurrence T(n) = T(n 1) + O(n)...

Transcribed Image Text:

8. Use the substitution method to prove that the recurrence T(n) = T(n 1) + O(n) has the solution T(n) = O(n), as claimed at the beginning of Section 7.2 in the textbook. Note I am asking for (n), not just O(n) or N(n). 9. Show that the running time of QUICKSORT is (n) when the elements of the input array are sorted in decreasing order. 10. In bounding RANDOMIZED-QUICKSORT, the textbook (on page 197) relies on the fact that har- monic numbers (the series H for increasing n) grows logarithmically with n: = n 1 [ k k=1 and A.20 and A.21 in the appendix show tighter bounds: In(n + 1) Hn (ln n) + 1 This is just one example of how summations of monotonic functions can be bounded by integrals, as illustrated (for monotonically increasing functions) in Figure A.1. Inn + O(n) n k k=1 1 You may recall that the exact solution for the sum of the series of squares is: n(n+1)(2n +1) 6 = But if you didn't know how to derive this exactly, what integral expressions would be upper and lower bounds on this sum of the series of squares, using the same approach as in Figure A.1? 8. Use the substitution method to prove that the recurrence T(n) = T(n 1) + O(n) has the solution T(n) = O(n), as claimed at the beginning of Section 7.2 in the textbook. Note I am asking for (n), not just O(n) or N(n). 9. Show that the running time of QUICKSORT is (n) when the elements of the input array are sorted in decreasing order. 10. In bounding RANDOMIZED-QUICKSORT, the textbook (on page 197) relies on the fact that har- monic numbers (the series H for increasing n) grows logarithmically with n: = n 1 [ k k=1 and A.20 and A.21 in the appendix show tighter bounds: In(n + 1) Hn (ln n) + 1 This is just one example of how summations of monotonic functions can be bounded by integrals, as illustrated (for monotonically increasing functions) in Figure A.1. Inn + O(n) n k k=1 1 You may recall that the exact solution for the sum of the series of squares is: n(n+1)(2n +1) 6 = But if you didn't know how to derive this exactly, what integral expressions would be upper and lower bounds on this sum of the series of squares, using the same approach as in Figure A.1?