Notice removed Draw attention by Karl Bielefeldt
Bounty Ended with Bart van Ingen Schenau's answer chosen by Karl Bielefeldt
Notice added Draw attention by Karl Bielefeldt
Bounty Started worth 100 reputation by Karl Bielefeldt
3 reformatted, typos fixed and retagged

# trying Trying to understand the 2N lnN compares for quicksort

I was going thruthrough the analysis of quicksort in Sedgewick's Algorithms book.He 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. I know it takes 1/N probability for any element to become the pivot and that if k becomes the pivot  ,then then the left subarraysub-array will have k-1 elements and right subarraysub-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 for each value of k  ,if if you add those up,the the probability that the partitioning element is k + the cost for the two subarrayssub-arrays you get the above equation..

Can someone explain this sothat 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?

• 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?

# trying to understand the 2N lnN compares for quicksort

I was going thru 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 subarray will have k-1 elements and right subarray 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 subarrays you get the above equation..

Can someone explain this sothat 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?

# Trying to understand the 2N lnN compares for quicksort

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?
2 added 99 characters in body

I was going thru 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 subarray will have k-1 elements and right subarray 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 subarrays you get the above equation..

Can someone explain this sothat 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?

I was going thru 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 subarray will have k-1 elements and right subarray 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 subarrays you get the above equation..

Can someone explain this sothat those with less math knowledge (me) can understand ?

I was going thru 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 subarray will have k-1 elements and right subarray 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 subarrays you get the above equation..

Can someone explain this sothat 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?

1

# trying to understand the 2N lnN compares for quicksort

I was going thru 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 subarray will have k-1 elements and right subarray 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 subarrays you get the above equation..

Can someone explain this sothat those with less math knowledge (me) can understand ?