Computer Science – Data Structures and Algorithms
Scientific paper
2008-11-26
Computer Science
Data Structures and Algorithms
15 pages;12figures;2 tables
Scientific paper
The paper questions the robustness of average case time complexity of the fast and popular quicksort algorithm. Among the six standard probability distributions examined in the paper, only continuous uniform, exponential and standard normal are supporting it whereas the others are supporting the worst case complexity measure. To the question -why are we getting the worst case complexity measure each time the average case measure is discredited?-- one logical answer is average case complexity under the universal distribution equals worst case complexity. This answer, which is hard to challenge, however gives no idea as to which of the standard probability distributions come under the umbrella of universality. The morale is that average case complexity measures, in cases where they are different from those in worst case, should be deemed as robust provided only they get the support from at least the standard probability distributions, both discrete and continuous. Regretfully, this is not the case with quicksort.
Chakraborty Soubhik
Sourabh Suman Kumar
No associations
LandOfFree
How robust is quicksort average complexity? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with How robust is quicksort average complexity?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How robust is quicksort average complexity? will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-274995