| Topic List | Page List: 1 |
|---|---|
| Topic | What is the numerical average number of comparisons in a quicksort (not Big O) |
| joe40001 06/20/20 5:38:43 AM #7: | Garioshi posted... Why not average the best and worst case scenarios? Here is what they will say: Average case: N log N Worst Cast N^2 So for 100 items they are arguing average case is (regular log) 200 or (natural log) 460, for worst case it is 10000. But the whole point of big oh notation is that it disregards any constant multiplier, so the literal expected value could be 200-450 billion to 10000 billion and since the billion multiplier is constant it won't affect shit in big oh. --- "joe is attractive and quite the brilliant poster" - Seiichi Omori https://imgur.com/TheGsZ9 ... Copied to Clipboard! |
| Topic List | Page List: 1 |