4 ms·
You're definitely not wrong, its generally the fastest. Efficient is a bit of a loaded worded in these contexts, and I feel as though when discussiing algorithm
by gms7777 13y ago
You're definitely not wrong, its generally the fastest. Efficient is a bit of a loaded worded in these contexts, and I feel as though when discussiing algorithms, unless otherwise specified, the assumption is you're discussing worst-case efficiency (because while worst case isn't always the most useful metric, is usually the most easily defined and derived one). And randomizing data doesn't necessarily guarantee that you won't still land on a worst-case starting order (as is the nature of randomness). As I said though, that is an entirely nitpicky point.
- lifebeyondfife 13y agoI see what you mean. Thanks for taking the time out to nitpick.
- eru 13y agoRandomized QuickSort has an expected worst case runtime of O(n log n). To pick that part, first you write your (randomized) QuickSort, then your antagonists picks the worst case, and last you let your algorithm run and pick its random numbers. No matter how the antagonist chooses the input (but not the random numbers), you get O (n log n) expected runtime. This is different from an average (over all inputs) run time.
- tubbzor 13y ago>And randomizing data doesn't necessarily guarantee that you won't still land on a worst-case starting order (as is the nature of randomness). This is the beauty of randomized analysis in the worst-cases. The worst-case occurs if and only if the random generator spits out a sorted list. If all permutations are equally likely, a list of n elements has probability 1/n! of coming out sorted = O(n^2). Even in practice, this is very pessimisstic as it only occurs with a probability of 1/n! and is therefore extremely rare.