3
$\begingroup$

In the book An Introduction to the Analysis of Algorithms there is a recurrence relation for the number of compares used in Quicksort algorithm: $$ C_N=N+1+\sum_{0≤k≤N-1}\frac{1}{N}(C_k+C_{N−k−1}) $$ (See http://aofa.cs.princeton.edu/10analysis/ for details)

This recurrence relation is already solved in the book: $$ C_N = 2(N+1)H_N - 2N,$$ where $ H_N $ are harmonic numbers.

Now I'm trying to solve it using Mathematica:

RSolve[{c[n] == n + 1 + 1/n*Sum[c[k] + c[n - k - 1], {k, 0, n - 1}], 
        c[0] == 0}, c[n], n]

Unfortunately, I can't get a result: RSolve just pretty prints input and doesn't solve anything.

Is there any way to solve such recurrences using Mathematica? Are there any other CASes which able to solve it?

$\endgroup$
5
$\begingroup$

You can define c[n] with

c[n_] := c[n] = n + 1 + 1/n*Sum[c[k] + c[n - k - 1], {k, 0, n - 1}]
c[0] = 0;

and then use FindSequenceFunction to find the desired solution:

FindSequenceFunction[Table[c[n], {n, 1, 10}], n]
2 (1 + n) (-1 + EulerGamma + PolyGamma[0, 2 + n])
FullSimplify@%
2 (1 + n) (-1 + HarmonicNumber[1 + n])
%% == 2 (n + 1) HarmonicNumber[n] - 2 n // FullSimplify
True
$\endgroup$
  • $\begingroup$ Dear Karsten, small question: what if instead of the condition c[0]=0 we had one of the kind c[n<2]=0, how do we express this in mathematica when defining and solving recurrence relations as you have exactly done in the above. Thanks in advance for any hints. $\endgroup$ – user21766 Jul 14 '17 at 13:33
  • $\begingroup$ @user929304 You can use a PatternTest, a Condition, or Piecewise. $\endgroup$ – Karsten 7. Jul 14 '17 at 20:10
  • $\begingroup$ In my answer I could have used, e. g., c[n_?(# <= 0 &)] = 0;, c[n_ /; n <= 0] = 0;, or c[n_] /; n <= 0 := c[n] = 0; instead of c[0] = 0; or just c[n_] := c[n] = \[Piecewise] { {0, n <= 0}, {n + 1 + 1/n*Sum[c[k] + c[n - k - 1], {k, 0, n - 1}], n > 0} } for both cases. $\endgroup$ – Karsten 7. Jul 14 '17 at 20:13

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.