Use the substitution method to prove that the recurrence T (n) = T (n - 1) + Θ(n) has the solution T (n) = Θ(n^2), as claimed at the beginning of Section 7.2.
T(n) = T(n-1) + Θ(n) = Θ(n) + Θ(n-1) + ... + Θ(1) = Θ(n^2)
Here is the substitution method:
Let's assume that T(n - 1) <= c(n-1)^2
Then T(n) <= c*(n-1)^2 + Θ(n)
<= c*n^2 -(2cn - Θ(n))
So we can find a c which is large enough to make
2cn > Θ(n),eg. assume Θ(n) = kn, then we make c > k/2
So T(n) <= c*n^2
T(n) = Θ(n^2)What is the running time of QUICKSORT when all elements of array A have the same value?
Θ(n^2)
Show that the running time of QUICKSORT is Θ(n^2) when the array A contains distinct elements and is sorted in decreasing order.
Similar to the above problem，because T(n) = T(n-1) + Θ(n)
The pivot value in quicksort is smaller than all of the other values, and hence can never achieve a balanced array in each recursive step.
Banks often record transactions on an account in order of the times of the transactions, but many people like to receive their bank statements with checks listed in order by check number. People usually write checks in order by check number, and merchants usually cash them with reasonable dispatch. The problem of converting time-of-transaction ordering to check-number ordering is therefore the problem of sorting almost-sorted input. Argue that the procedure INSERTION-SORT would tend to beat the procedure QUICKSORT on this problem.
原数组越有序，逆序对越少，插入排序越快.
The more ordered the original array, the less the inversions and Insertion Sort will run much more quickly.
INSERTION-SORT's while loop which checks for whether or not a new insertion needs to be done would stop after only one iteration, and in addition quicksort would not be able to achieve a balanced split at every recursive step due to the pivot being the largest number in the new array to sort.
Suppose that the splits at every level of quicksort are in the proportion 1 - α to α, where 0 < α ≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - lg n/ lg α and the maximum depth is approximately -lg n/ lg(1 - α). (Don't worry about integer round-off.)
First calculate the minimum height:
As for the maximum height, replace α with (1 - α)
Argue that for any constant 0 < α ≤ 1/2, the probability is approximately 1 - 2α that on a random input array, PARTITION produces a split more balanced than 1-α to α.
因为比1-α to α更好的分布的数的在他们之间，有1 - 2α的比例.比他们差的有α＋α ＝ 2α
The number better than [1-α,α] among them, and has a propotion 1 - 2α. So number worse than then is 2α
Follow @louis1992 on github to help finish this task.