Write a recurrence relation for this modified Quicksort?
up vote
0
down vote
favorite
In a modified quicksort, you partition randomly on odd levels of recursive calls and on even levels you partition on the largest element. How do you write a recurrence relation for exactly how many comparisons quicksort will do?
algorithm quicksort relation recurrence
asked Nov 11 at 17:52
Michael Lin
102
add a comment |
up vote
0
down vote
favorite
In a modified quicksort, you partition randomly on odd levels of recursive calls and on even levels you partition on the largest element. How do you write a recurrence relation for exactly how many comparisons quicksort will do?
algorithm quicksort relation recurrence
asked Nov 11 at 17:52
Michael Lin
102
Exactly sounds a little weird when you consider a random variable ?!
– Yves Daoust
Nov 11 at 18:11
Can you provide the recurrence relation for the case of ordinary Quicksort ?
– Yves Daoust
Nov 11 at 18:12
Yes. T(n) = T(n/4) + T(3n/4) + (n-1) for average case.
– Michael Lin
Nov 12 at 0:36
Then it suffices to add a term n-1 to find the largest element, then another term n-1 to perform the partition with this pivot, and replace n by n-1, as the partition will just leave the largest element apart. T(n)=2(n-1)+T((n-1)/4)+T(3(n-1)/4)+(n-2).
– Yves Daoust
Nov 12 at 13:49
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
In a modified quicksort, you partition randomly on odd levels of recursive calls and on even levels you partition on the largest element. How do you write a recurrence relation for exactly how many comparisons quicksort will do?
algorithm quicksort relation recurrence
asked Nov 11 at 17:52
Michael Lin
102
In a modified quicksort, you partition randomly on odd levels of recursive calls and on even levels you partition on the largest element. How do you write a recurrence relation for exactly how many comparisons quicksort will do?
algorithm quicksort relation recurrence
algorithm quicksort relation recurrence
asked Nov 11 at 17:52
Michael Lin
102
asked Nov 11 at 17:52
Michael Lin
102
asked Nov 11 at 17:52
Michael Lin
102
asked Nov 11 at 17:52
Michael Lin
102
asked Nov 11 at 17:52
Michael Lin
102
102
Exactly sounds a little weird when you consider a random variable ?!
– Yves Daoust
Nov 11 at 18:11
Can you provide the recurrence relation for the case of ordinary Quicksort ?
– Yves Daoust
Nov 11 at 18:12
Yes. T(n) = T(n/4) + T(3n/4) + (n-1) for average case.
– Michael Lin
Nov 12 at 0:36
Then it suffices to add a term n-1 to find the largest element, then another term n-1 to perform the partition with this pivot, and replace n by n-1, as the partition will just leave the largest element apart. T(n)=2(n-1)+T((n-1)/4)+T(3(n-1)/4)+(n-2).
– Yves Daoust
Nov 12 at 13:49
add a comment |
Exactly sounds a little weird when you consider a random variable ?!
– Yves Daoust
Nov 11 at 18:11
Can you provide the recurrence relation for the case of ordinary Quicksort ?
– Yves Daoust
Nov 11 at 18:12
Yes. T(n) = T(n/4) + T(3n/4) + (n-1) for average case.
– Michael Lin
Nov 12 at 0:36
Then it suffices to add a term n-1 to find the largest element, then another term n-1 to perform the partition with this pivot, and replace n by n-1, as the partition will just leave the largest element apart. T(n)=2(n-1)+T((n-1)/4)+T(3(n-1)/4)+(n-2).
– Yves Daoust
Nov 12 at 13:49
Exactly sounds a little weird when you consider a random variable ?!
– Yves Daoust
Nov 11 at 18:11
Exactly sounds a little weird when you consider a random variable ?!
– Yves Daoust
Nov 11 at 18:11
Can you provide the recurrence relation for the case of ordinary Quicksort ?
– Yves Daoust
Nov 11 at 18:12
Can you provide the recurrence relation for the case of ordinary Quicksort ?
– Yves Daoust
Nov 11 at 18:12
Yes. T(n) = T(n/4) + T(3n/4) + (n-1) for average case.
– Michael Lin
Nov 12 at 0:36
Yes. T(n) = T(n/4) + T(3n/4) + (n-1) for average case.
– Michael Lin
Nov 12 at 0:36
Then it suffices to add a term n-1 to find the largest element, then another term n-1 to perform the partition with this pivot, and replace n by n-1, as the partition will just leave the largest element apart. T(n)=2(n-1)+T((n-1)/4)+T(3(n-1)/4)+(n-2).
– Yves Daoust
Nov 12 at 13:49
Then it suffices to add a term n-1 to find the largest element, then another term n-1 to perform the partition with this pivot, and replace n by n-1, as the partition will just leave the largest element apart. T(n)=2(n-1)+T((n-1)/4)+T(3(n-1)/4)+(n-2).
– Yves Daoust
Nov 12 at 13:49
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53251531%2fwrite-a-recurrence-relation-for-this-modified-quicksort%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Exactly sounds a little weird when you consider a random variable ?!
– Yves Daoust
Nov 11 at 18:11
Can you provide the recurrence relation for the case of ordinary Quicksort ?
– Yves Daoust
Nov 11 at 18:12
Yes. T(n) = T(n/4) + T(3n/4) + (n-1) for average case.
– Michael Lin
Nov 12 at 0:36
Then it suffices to add a term n-1 to find the largest element, then another term n-1 to perform the partition with this pivot, and replace n by n-1, as the partition will just leave the largest element apart. T(n)=2(n-1)+T((n-1)/4)+T(3(n-1)/4)+(n-2).
– Yves Daoust
Nov 12 at 13:49