Notice removed Draw attention by Karl Bielefeldt
    Bounty Ended with Bart van Ingen Schenau's answer chosen by Karl Bielefeldt
    Tweeted twitter.com/#!/StackProgrammer/status/364489087245647872
    Notice added Draw attention by Karl Bielefeldt
    Bounty Started worth 100 reputation by Karl Bielefeldt
3 reformatted, typos fixed and retagged
source | link

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.

enter image description here

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.

enter image description here

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.

enter image description here

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
source | link

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.

enter image description here

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.

enter image description here

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.

enter image description here

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
source | link

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.

enter image description here

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 ?