Question on computing the average time of Quicksort

The question comes from the following wikipedia entry

http://en.wikipedia.org/wiki/Quicksort

"Average complexity
Even if pivots aren't chosen randomly, quicksort still requires only
Θ(nlogn) time over all possible permutations of its input. Because
this average is simply the sum of the times over all permutations of
the input divided by n factorial, it's equivalent to choosing a random
permutation of the input. When we do this, the pivot choices are
essentially random, leading to an algorithm with the same running time
as randomized quicksort.

More precisely, the average number of comparisons over all
permutations of the input sequence can be estimated accurately by
solving the recurrence relation:"

I don't see how they arrive at the recurrence relation. If there are
n-1 comparisons, I thought it would be

for i=0 to n-1

C(n) = 1/n * (sum(c(n - i - 1))

I don't get were the n-1 and C(i) terms come from.

Can someone clarify this?

Thank you.
.

Relevant Pages

  • Re: paper claiming projective planes must have prime power order
    ... then n must be a prime power. ... Consider the n(n-1) rows of n-1 Latin squares of order n as a set of ... permutations in the group of permutations S_n. ...
    (sci.math)
  • Re: paper claiming projective planes must have prime power order
    ... then n must be a prime power. ... Consider the n(n-1) rows of n-1 Latin squares of order n as a set of ... permutations in the group of permutations S_n. ...
    (sci.math)
  • Re: permutations [was:Re: decrementing arrays]
    ... Permutations are easy, although it doesn't seem like it at first. ... The first group consists of all those permutations that start with ... For each group, you now have one of its members positioned, and another N-1 ... You must permute all of those N-2 items. ...
    (comp.lang.c)
  • Re: permutations [was:Re: decrementing arrays]
    ... Permutations are easy, although it doesn't seem like it at first. ... The first group consists of all those permutations that start with ... For each group, you now have one of its members positioned, and another N-1 ... You must permute all of those N-2 items. ...
    (comp.lang.c)