Current Events > What is the numerical average number of comparisons in a quicksort (not Big O)

(+) Yeah! (+)

I want to apply it to get the expected value of a number of comparisons of a list of size n, but I know n log n is not exactly right. So what is it?

For example, I highly doubt a list of 100 will have on average 200 comparisons. Is it n ln n? Is it n logbase2 n? Is it 2n ln 4n?

How fast it scales is useless to me in me trying to get a practical example.

I can't for the life of me find a google result that isn't just telling me the big o result which of course everybody knows.

---

You're not going to get an exact answer since it depends on your data set and your implementation. You can treat f(x) = O(g(x)) as an approximation of sorts for particular x anyways, which makes sense from the limit definition.

For instance, a quick Google search says you can on average expect O(n log n) operations. So for 100 items, you can expect roughly 100 log(100) 461 operations.

---

Just average traditional implementation is all I'm asking about. Quick sort is very well known so what i mean by it should be fairly clear.

Also 100log100 = 200 not 461

You might have meant 100ln100, but the fact we can be off by over 100% on such a well researched question is what confuses me.

---

I'm used to referencing log as natural log in lieu of base 10, and that was what the Wikipedia article said IIRC (that it was ln). So my bad there.

---

Eevee-Trainer posted...

I'm used to referencing log as natural log in lieu of base 10, and that was what the Wikipedia article said IIRC (that it was ln). So my bad there.

It's fine but that's kinda my point here. If I want to do anything near precise math of expected value, all answers are like 100log100 200 but maybe 400 or 80 or 890,000,000.

I don't care how it scales with N, I want a realistic approximation of what it is for a given N

---

joe40001 posted...

It's fine but that's kinda my point here. If I want to do anything near precise math of expected value, all answers are like 100log100 200 but maybe 400 or 80 or 890,000,000.

I don't care how it scales with N, I want a realistic approximation of what it is for a given N

Why not average the best and worst case scenarios?

---

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.

---