Hi guys, may please I get a good analogy PLEASE why choosing the pivot of quicksort would effectively affect my time complexity? what about if I choose the pivot randomly , what happen to my time complexity?! **I know it would be changed .. but I don't know why .. from equations yeah it would be changed .. I want a good analogy sense for feeling comfortable while solving .. **
I'm trying to imagine if I have a cake but not circular it's rectangle and a specific piece of cake that I want is found on "the middle" of the rectangle of the cake .. in two cases I get the same time to search on that specific piece cake ..


thanks alot !!

 

Hi guys, may please I get a good analogy PLEASE why choosing the pivot of quicksort would effectively affect my time complexity? what about if I choose the pivot randomly , what happen to my time complexity?! **I know it would be changed .. but I don't know why .. from equations yeah it would be changed .. I want a good analogy sense for feeling comfortable while solving .. **
I'm trying to imagine if I have a cake but not circular it's rectangle and a specific piece of cake that I want is found on "the middle" of the rectangle of the cake .. in two cases I get the same time to search on that specific piece cake ..


thanks alot !!

Consider some of the alternatives.

What would happen if you chose as your pivot value the minimum of the maximum value in the data set?

What would happen if you chose as your pivot the median value in the data set?

What is the ideal choice for the pivot?

Why don't we use that as the standard choice?

If you choose the pivot randomly, how likely are you to be close to the ideal choice?

Are there simply ways of choosing a pivot that should, on average, put you closer to the ideal choice than a random choice would?