# Number of calls with length 2 array in quick-sort

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);
}

• This depends very much on the actual implementatin of Quicksort. For good implementations, the number is zero. – gnasher729 Apr 22 '18 at 19:02
• @gnasher729 Thanks very much for your comment. That was my mistake to not include the implementation. I updated the post. – Yola Apr 23 '18 at 8:12
• There seems to be an error in your calculation of $T_5$. You're using a value of $5/4$ instead of $5/6$ for $T_4$. If you use the correct value, you get $T_5 = 1$. – Yuval Filmus Apr 23 '18 at 20:49

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}.$$