The 1st time P is called, c is increased by N+1
The 2nd time P is called, c is increased by N
The 3rd time P is called, c is increased by N-1
...
The (N-1)th time P is called, c is increased by 3

So, the final value of C is (sum of A.P.)
((N+1)+3)*(N-1) div 2
=(N*N+3*N-4) div 2

But I really don't know how it's thought out.

Thanks for your comments.

Here is what I thought:

** I see it is quicksort

** I know that when the input is sorted, quicksort become a bubblesort(only one side is split each time), that make it easier to think about

** then, use recursive function which fill the entire array, and the result is just a sorted array. If start from 1, it will be 1 2 3 4 .......N

But you provide a math provef of how they match:)

What a wonderful explanation!

Edited by author 06.01.2008 17:36

The 1st time P is called, c is increased by N+1
The 2nd time P is called, c is increased by N
The 3rd time P is called, c is increased by N-1
...
The (N-1)th time P is called, c is increased by 3

I don't get it how You came to this analysis? Did You write a program to get how much is c increased the 1st the 2nd and the 3rd time? Why is P called N-1th times?
Can somebody please explain me how QS works - I know it divides the array in left:medium:right
But I guess medium is just always only one element. Am I correct?
Please enlighten me.  Thanks ...

Edited by author 03.03.2011 16:54

Edited by author 03.03.2011 16:54

Hi,
      The iteration stops always after 3 comparisons for the pivot element in quicksort. Hence last element of AP is 3. First time iteration is always (N+1). Now  number of elments of AP is N-1. Thus the formula proves to be true.

Regards
Anupam

In an ideal case first you should have paid attention to N*N in c's expression. then u realize that answer should be some of the wort-case inputs for QS (one of which being   already sorted array).
then u copy the procedure and check ur hyphothesis for all N = 1 to 1000. no need to think it over really.