CODEWITHSUNDEEP
algorithmcomplexity-theoryquicksort
Mary Star
Mary Star

Reputation: 375

which is the cost of the average case?

According to my notes,we find the cost of the average case of the quicksort,like that:

We suppose that we are lucky-unlucky alternately. L: lucky U:Unlucky

Then,these two relations:

L(n)=2U(n/2)+Θ(n) ,
U(n)=L(n-1)+ Θ(n)

So, L(n)=Θ(n lg n)

At an other page of my notes,the cost of the average case is given by the following relation:

T(n)=min_{1<=q<=n} {T(q)+T(n-q)}+Θ(n)

So,are these two relations equivalent or is there a difference?

Upvotes: 0

Views: 93

Answers (1)

duncanm
duncanm

Reputation: 796

Caveat: This is not really an answer, more a long comment.

You're missing a couple of steps between the first pair of relations ( L(n) = ... and U(n) = ...) and the conclusion (that for this particular situation --- i.e. alternating lucky-unlucky --- the performance is O(n lg n) ). With those steps filled in, you have a kind of 'intuitive' argument for why the average case performance of quicksort is Θ(n lg n). That is, we might expect something like half our pivots to be 'good' and half to be 'bad', and in the extreme case where half of the pivots are "as good as possible" and half are "as bad as possible", performance is still O(n lg n) (but presumably with a different constant term to the actual average case).

The second relation you give (i.e. minimising the T(q) + T(n-q) over q) looks more like the beginnings of a best case analysis to me, rather than an average case analysis. For that, I'd expect something more like:

T(n) = (1/n) sum_{i=1}^{n-1} ( T(n-i) + T(i) ) + Θ(n)

It might be worth googling for a few more analyses...

Upvotes: 2

Related Questions