1
$\begingroup$

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);
}
$\endgroup$
  • 1
    $\begingroup$ This depends very much on the actual implementatin of Quicksort. For good implementations, the number is zero. $\endgroup$ – gnasher729 Apr 22 '18 at 19:02
  • $\begingroup$ @gnasher729 Thanks very much for your comment. That was my mistake to not include the implementation. I updated the post. $\endgroup$ – Yola Apr 23 '18 at 8:12
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Apr 23 '18 at 20:49
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.