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$
3
  • 1
    $\begingroup$ This depends very much on the actual implementatin of Quicksort. For good implementations, the number is zero. $\endgroup$
    – gnasher729
    Apr 22, 2018 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, 2018 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$ Apr 23, 2018 at 20:49

1 Answer 1

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 and acknowledge you have read our privacy policy.

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