Number of calls with length 2 array in quick-sort

Question

I need to find average number of recursive calls in quick-sort with array of length 2. I established and solved the following recursion:

$$T_N = \frac{1}{N}\sum_{k=1}^N\left(T_{k-1}+N_{N-k}\right) = \frac{N+1}{N}T_{N-1} = \frac{N+1}{3}.$$

Where $T_0 = T_1 = 0, T_2 = 1$. But:

\begin{align*} T_3 &= 1/3(1 + 1) &= 2/3\\ T_4 &= 1/4(2/3 + 1 + 1 + 2/3) &= 5/6\\ T_5 &= 1/5 (5/4 + 2/3 + 2 + 2/3 + 5/4) &= 7/6\\ T_6 &= 1/6(7/6 + 5/6 + (1+2/3) + (1+2/3) + 5/6 + 7/6) &= 11/9 \end{align*}

The results are different. How to do it right?

EDIT: The code for quick-sort in question is:

void quicksort(int[] a, int lo, int hi)
{
  if (hi <= lo) return;
  int i = lo-1, j = hi;
  int t, v = a[hi];
  while (true) {
    while (a[++i] < v) ;
    while (v < a[--j]) if (j == lo) break;
    if (i >= j) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
  }
  t = a[i]; a[i] = a[hi]; a[hi] = t;
  quicksort(a, lo, i-1);
  quicksort(a, i+1, hi);
}

Answer 1

First, note that you can write your recurrence as $$ T_N = \frac{2}{N}\sum_{i=0}^{N-1} T_i. $$ Consider now the generating function $$ T(x) = \sum_{N=0}^\infty T_N x^N. $$ We calculate $$ \frac{T(x)}{1-x} = \sum_{N=0}^\infty \sum_{i=0}^N T_i x^N = \frac{1}{2} \sum_{N=2}^\infty (N+1)T_{N+1}x^N = \frac{1}{2} \sum_{N=3}^\infty NT_Nx^{N-1}. $$ On the other hand, $$ \frac{d}{dx} T(x) = \sum_{N=0}^\infty NT_Nx^{n-1}. $$ We conclude that $T(x)$ satisfies the differential equation $$ \frac{d}{dx} T(x) = \frac{2T(x)}{1-x} + 2x. $$ Additionally, $T(0) = 0$. Plugging this into Wolfram alpha, we obtain the solution $$ T(x) = \frac{x^2(3x^2-8x+6)}{6(1-x)^2}. $$ Using $1/(1-x)^2 = \sum_{N=0}^\infty (N+1)x^N$, we obtain for $N \geq 3$ that $$ T_N = \frac{6(N-1)-8(N-2)+3(N-3)}{6} = \frac{N+1}{6}. $$

---

Having computed the solution by brute force, it is easy to prove by induction. Suppose that $N \geq 3$. Then $$ T_N = \frac{2}{N} \sum_{i=0}^{N-1} T_i = \frac{2}{N} \left(1 + \sum_{i=3}^{N-1} \frac{i+1}{6}\right) = \frac{2}{N} \left(1 + \frac{(N-3)(N+4)}{12} \right) = \frac{N+1}{6}. $$