I was going through the analysis of quicksort in Sedgewick's Algorithms book. He creates the following recurrence relation for number of compares in quicksort while sorting an array of N distinct items.
I am having a tough time understanding this... I know it takes 1/N probability for any element to become the pivot and that if k becomes the pivot, then the left sub-array will have k-1 elements and right sub-array will have N-k elements.
1.How does the cost of partitioning become N+1 ? Does it take N+1 compares to do the partitioning?
2.Sedgewick says, for each value of k, if you add those up, the probability that the partitioning element is k + the cost for the two sub-arrays you get the above equation.
- Can someone explain this so that those with less math knowledge (me) can understand?
- Specifically how do you get the second term in the equation?
- What exactly does that term stand for?