Basic Recurrence Problem in the Analysis of Algorithm

Question

I am taking an algorithm course at Coursera. From this webpage by a Princeton Professor, Example 1.5 (Analysis of quicksort) gives the following codes.

public class Quick

{

private static int partition(Comparable[] a, int lo, int hi)

{

int i = lo, j = hi+1;

while (true)

{

   while (less(a[++i], a[lo])) if (i == hi) break;

   while (less(a[lo], a[--j])) if (j == lo) break;

   if (i >= j) break;

   exch(a, i, j);

}

exch(a, lo, j);

return j;

}

private static void sort(Comparable[] a, int lo, int hi)

{

if (hi <= lo) return;

int j = partition(a, lo, hi);

sort(a, lo, j-1);

sort(a, j+1, hi);

}

}

Define $C_N$ to be the number of compares to sort $N$ elements and analyze $C_N$. Then,

$C_N = N+1+\frac{2}{N}\sum\limits_{0\leq k\leq N-1} C_k$ is equivalent to

$NC_N=(N+1)N+2\sum\limits_{0\leq k\leq N-1} C_k$, which is equivalent to

$NC_N-(N-1)C_{N-1}=N(N+1)-(N-1)N+2C_{N-1}$.

Questions

I could not derive the third equation from the second. Indeed, if they are equivalent, then $2(C_o + C_1 + \dots +C_{N-1})=(N-1)(C_{N-1} -N)$. Is it true?

Also, the definition of $C_N$ looks a little fuzzy to me. In fact, I have googled the definition of "compares" for a while, but still could not understand it completely. Does $C_N$ define the number of comparisons we would make in order to compare $N$ elements? (Yes, this is my first algorithm course, and I have no java background.)

Answer 1

The second equation says that $$2(C_0+C_1+\cdots+C_{N-1})=D_N\tag{1}$$ where we define $$D_N=NC_N-N(N+1).$$ Replacing $N$ by $N-1$ in (*) gives $$2(C_0+C_1+\cdots+C_{N-2})=D_{N-1}.\tag{2}$$ Subtracting (2) from (1) gives $$2C_{N-1}=D_N-D_{N-1}.\tag{3}$$ That's your third equation.

From (3) one has $$2(C_0+C_1+\cdots+C_{N-1}) =(D_1-D_0)+(D_2-D_1)+\cdots+(D_N-D_{N-1})=D_N-D_0.$$ But $D_0=0C_0-0=0$ so this recovers (1).